当前位置：首页 > 分类 > JAVA基础 > JDK源码-LinkedList

JDK源码-LinkedList

LinkedList类其实没什么好说的，唯有数据结构与ArrayList不同，其他大致相同。如transient，ConcurrentModificationException，fail-fast，Serializable。因为数据结构不同，LinkedList没有扩容的概念。

1，下面看下数据结构

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

三个成员变量，分别记录链表的元素个数，表头，表尾。均被transient修饰。

2，节点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;
        }
    }

记录自己的数据，以及前一个节点和后一个节点，所以是双向链表，可从头向尾遍历，也可从尾向头遍历。

3，add

     public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    第一个方法默认添加到表尾。

    第二个方法添加到传入节点的前面。

4.remove

public E remove() {
  return removeFirst();
}

 public E remove(int index) {
   checkElementIndex(index);
   return unlink(node(index));
}

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

第一个方法无参默认删除表头元素。

第二个方法int（注意不是integer，否则会调用第三个方法）删除int下标位置的元素。需要遍历。

第三个方法删除指定元素。需要遍历。

public static void main(String[] args) {
		LinkedList<Integer> a = new LinkedList<>();
		a.add(1);//index0
		a.add(2);//index1
		a.add(3);//index2
		a.add(4);//index3
		Integer b =1;
		a.remove(b);
		System.out.println(a.toString());
	}

结果

[2, 3, 4]

这里传的Integer b，删除的是等于1的元素，而不是下标为1的元素。

5，toString（）继承自AbstractCollection类

 public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

所以不需要自己遍历。