LinkedList类

  • 链表结构实现,增删快,查询慢。

1. LinkedList

LinkedList<Student> linkedList = new LinkedList<>();
Student s1 = new Student("唐", 21);
Student s2 = new Student("何", 22);
Student s3 = new Student("余", 21);
// 1.添加元素
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
linkedList.add(s3);
System.out.println("元素个数:" + linkedList.size());
System.out.println(linkedList.toString());
// 2.删除元素
/*
         * linkedList.remove(new Student("唐", 21));
         * System.out.println(linkedList.toString());
         */
// 3.遍历
// 3.1 使用for
for (int i = 0; i < linkedList.size(); ++i) {
  System.out.println(linkedList.get(i));
}
//3.2 使用增强for
for (Student student : linkedList) {
  System.out.println(student.toString());
}
// 3.3 使用迭代器
Iterator<Student> iterator = linkedList.iterator();
while (iterator.hasNext()) {
  System.out.println(iterator.toString());
}
// 3.4 使用列表迭代器(略)
// 4. 判断
System.out.println(linkedList.contains(s1));
System.out.println(linkedList.isEmpty());
System.out.println(linkedList.indexOf(s3));

2. LinkedList源码分析

LinkedList首先有三个属性:

  • 链表大小:transient int size = 0;
  • (指向)第一个结点/头结点:transient Node<E> first;
  • (指向)最后一个结点/尾结点:transient Node<E> last;

关于Node类型我们再进入到类里看看:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

首先item存放的是实际数据;next指向下一个结点而prev指向上一个结点。

Node带参构造方法的三个参数分别是前一个结点、存储的数据、后一个结点,调用这个构造方法时将它们赋值给当前对象。

LinkedList是如何添加元素的呢?先看看add方法:

public boolean add(E e) {
    linkLast(e);
    return true;
}

进入到linkLast方法:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-05-18 16:24:00

results matching ""

    No results matching ""