前言
工作中linkList用的次数相较于ArrayList少很多，可能因为用到List场景中多以查询为主的导致的。但是在面试中经常会被问到linkList和ArrayList的区别，就感觉像是，哥虽然不常在江湖，但是江湖总会有哥的传说一般。

正文

extends

linkList继承了 AbstractSequentialList

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

Java 集合深入理解（8）：AbstractSequentialList_qq_32440951的博客-CSDN博客_abstractsequentiallist

变量

 transient int size = 0;

    
    //头节点
    transient Node first;

    
    //尾节点
    transient Node last;

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

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

通过变量和名称其实我们可以猜测，linkList是通过Node组成的链表，继续往下，进行验证

构造方法

   
    public linkedList() {
    }

  
    public linkedList(Collection c) {
        this();  //调用上面的空构造方法
        addAll(c); //继续往下
    }

添加

 
    //在头节点之前添加
    public void addFirst(E e) {
        linkFirst(e);
    }

  
    private void linkFirst(E e) {
        final Node f = first;
       //定义一个新节点，新节点的下一个节点是当前链表的头节点
        final Node newNode = new Node<>(null, e, f); 
        //头节点变为当前节点
        first = newNode;
        if (f == null) //如果老的头节点为空，代表当前链表为空，所以设置尾节点为当前节点
            last = newNode;
        else
            //设置老的头节点的上一个节点为新节点
            f.prev = newNode;
        size++;
        modCount++;
    }


    //在尾节点的后添加
    public void addLast(E e) {
        linkLast(e);
    }

      
    void linkLast(E e) {
        final Node l = last;
           //定义一个新节点，新节点的前一个节点是当前链表的尾节点
        final Node newNode = new Node<>(l, e, null);
        //尾节点变为当前节点
        last = newNode;
        if (l == null) //如果老的尾节点为空，代表当前链表为空，所以设置头节点为当前节点
            first = newNode;
        else
            //老的尾节点的下一个节点设为当前节点
            l.next = newNode;
        size++;
        modCount++;
    }


 //相当于尾插入
public boolean add(E e) {
        linkLast(e); //上面
        return true;
    }
//批量尾插入
public boolean addAll(Collection c) {
        return addAll(size, c);
    }
    
public boolean addAll(int index, Collection c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node pred, succ;
        //根据index找到要查到位置的节点succ，和他的上一个节点 pred
        if (index == size) {
            succ = null; 
            pred = last;
        } else {
            succ = node(index); //查找当前位置的节点，具体请往下看
            pred = succ.prev;
        }

        //遍历集合形成的数组
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);
            if (pred == null) //如果pred为空，说明succ是头节点，所以头节点变为插入的第一个新节点
                first = newNode;
            else 
                pred.next = newNode; //如果pred不为空，则pred的下一个节点，为newNode
            pred = newNode;  //pred指向newNodde 以此类推
        }

        if (succ == null) { //如果succ为空，说明原来应该是空链表，所以链表的尾节点变尾pred
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

 //如果index的值不在链表的范围内，报错
 private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

 
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }


    
    Node node(int index) {
        // assert isElementIndex(index);
        //先二分下当前的
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

clone

clone 的源代码

   //浅克隆
    public Object clone() {
        linkedList clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }

关于深copy和浅copy的代码验证，参考上一章ArrayList

public static void main(String[] args) {
	
        linkedList list=new linkedList<>();
		//添加两个元素
		Student stJack=new Student("Jack", 13);
		Student stTom=new Student("Tom", 15);
		list.add(stJack);
		list.add(stTom);
		//深克隆
		linkedList listCopy=new linkedList();
		for (Student student : list) {
			listCopy.add(student.clone());
		}
		//移除且不修改
		listCopy.get(0).setAge(20);
		System.out.println(list);
		System.out.println(listCopy);

		//添加两个元素
		linkedList list2=new linkedList();
		list2.add(stJack);
		list2.add(stTom);
//克隆
		linkedList listCopy2= (linkedList) list2.clone();
//移除且不修改
		listCopy2.remove(1);
		System.out.println(list2);
		System.out.println(listCopy2);
		listCopy2.get(0).setAge(15);
		System.out.println(list2);
		System.out.println(listCopy2);
	}

移除

//移除头节点
public E removeFirst() {
        final Node f = first;
        if (f == null) //判断当前集合是否是空集合
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node next = f.next;
        //将当前节点前后全部清除
        f.item = null;
        f.next = null; // help GC
        first = next;  //然后首节点变为next
        if (next == null) //如果next == null 说明原来链表只有一个节点，所以移除后，链表变为 //空
            last = null;
        else
            next.prev = null; //next的上一个节点置为空，因为他作为首节点了
        size--; //大小减一
        modCount++;
        return element;
    }

//移除尾节点
public E removeLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

private E unlinkLast(Node l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--; //大小-1
        modCount++;
        return element;
    }

//移除固定对象
 public boolean remove(Object o) {
  //遍历集合，然后移除左边第一个相同的
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        //得到x的上一个和下一个
        final Node next = x.next;
        final Node prev = x.prev;

        if (prev == null) { //当前节点是否是首节点
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {  //当前节点是否是尾节点
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--; //大小 -1
        modCount++;
        return element;
    }
  
   //移除固定位置
   public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

//默认移除，移除的是首节点
public E remove() {
        return removeFirst();
    }

队列

linkList实现了Deque相关接口，所以可以作为队列来使用

相关队列方法

//先看下队列相关方法， 以下具体英文注释请看源码
public interface Deque extends Queue {
    //上面 “添加” 介绍了
    void addFirst(E e);

    //上面“添加” 介绍了
    void addLast(E e);

    //在此列表前面加入元素 里面代码用到addFirst(E e)
    boolean offerFirst(E e);

    //在此列表后面加入元素 调用了addLast(E e)
    boolean offerLast(E e);

    //上面移除介绍了 
    E removeFirst();

    //上面移除介绍了
    E removeLast();

    //弹出首节点，  
    // 先找到头节点， 调用unlinkFirst(Node e)
    E pollFirst();

    //弹出尾节点 
    // 先找到尾节点 调用unlinkLast(Node 3)
    E pollLast();

    //获取头，但不删除，如果节点为空 报 NoSuchElementException
    // fist.item
    E getFirst();

    //获取尾，但不删除， 报 NoSuchElementException
    // last.item
    E getLast();

    //获取头节点， 但不删除 和上面的getFirst区别于，节点为null时返回null, 不报错
    // first.item 
    E peekFirst();

    //获取尾，但不删除， 和上面的getLast区别于，节点为null时返回null, 不报错
    // last.item    
    E peekLast();

    //移除第一个匹配对象的o的节点， 调用 remove(Object o)
    boolean removeFirstOccurrence(Object o);

    //移除第一个匹配对象的Object的节点， 查找方法时从last向前查找，与remove相反
    boolean removeLastOccurrence(Object o);
    //linkList具体实现如下
    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    // *** Queue methods ***

    //请回顾上面的添加模块
    boolean add(E e);

    //添加元素。在队尾添加，调用add(E e)
    boolean offer(E e);

    //请回顾上面的移除模块
    E remove();

    //含义和poFirst相同
    E poll();

   //获取头节点的元素， 调用了addFirst
    E element();

    //含义和peekFirst相同
    E peek();


    //首部插入， 调用addFirst
    void push(E e);

    //移除首节点，并返回 调用removeFirst
    E pop();


    //请回顾移除模块
    boolean remove(Object o);

    //调用的indexOf(Object 0) 
    boolean contains(Object o);
    //具体代码如下， 从头节点遍历
     public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

  ....

}

JAVA源码学习之集合-LinkList

前言
工作中linkList用的次数相较于ArrayList少很多，可能因为用到List场景中多以查询为主的导致的。但是在面试中经常会被问到linkList和ArrayList的区别，就感觉像是，哥虽然不常在江湖，但是江湖总会有哥的传说一般。

正文

extends
linkList继承了 AbstractSequentialList

public class linkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

Java 集合深入理解（8）：AbstractSequentialList_qq_32440951的博客-CSDN博客_abstractsequentiallist

构造方法
public linkedList() { } public linkedList(Collection c) { this(); //调用上面的空构造方法 addAll(c); //继续往下 }

clone

Java相关栏目本月热门文章

JAVA源码学习之集合-LinkList

前言 工作中linkList用的次数相较于ArrayList少很多，可能因为用到List场景中多以查询为主的导致的。 但是在面试中经常会被问到linkList和ArrayList的区别， 就感觉像是，哥虽然不常在江湖，但是江湖总会有哥的传说一般。

正文

extends linkList继承了 AbstractSequentialList public class linkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable Java 集合深入理解（8）：AbstractSequentialList_qq_32440951的博客-CSDN博客_abstractsequentiallist

构造方法 public linkedList() { } public linkedList(Collection c) { this(); //调用上面的空构造方法 addAll(c); //继续往下 }

clone

Java相关栏目本月热门文章

前言
工作中linkList用的次数相较于ArrayList少很多，可能因为用到List场景中多以查询为主的导致的。但是在面试中经常会被问到linkList和ArrayList的区别，就感觉像是，哥虽然不常在江湖，但是江湖总会有哥的传说一般。

extends
linkList继承了 AbstractSequentialList

public class linkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

Java 集合深入理解（8）：AbstractSequentialList_qq_32440951的博客-CSDN博客_abstractsequentiallist

构造方法
public linkedList() { } public linkedList(Collection c) { this(); //调用上面的空构造方法 addAll(c); //继续往下 }