目录

1.linkedList  的源码研究

1，继承关系

2，构造函数

3，属性信息

4，底层数据结构

5，常用方法研究

2.linkedList 方法的使用

1，继承关系

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

2，构造函数

// 构造一个空列表 
public linkedList() {
 }


// 通过集合实例来实例化linkedList
 public linkedList(Collection c) {
     this();
      // 添加指定元素的列表
     addAll(c);
 }

3，属性信息

    // 用来记录linkedList的大小
    transient int size = 0;

    // 用来标记头节点
    transient Node first;

    // 用来标记尾巴节点
    transient Node last;

4，底层数据结构

底层数据结构是双向链表。

 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;
        }
    }

5，常用方法研究

add(E e)

// 默认添加到集合的末尾
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
// 尾部添加
    void linkLast(E e) {
// 标记尾巴节点
        final Node l = last;
// 添加新节点在尾部，前驱为l，后继为null
        final Node newNode = new Node<>(l, e, null);
//更新尾巴节点
        last = newNode;
// 判断链表是否为空
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
//linkedList长度加1
        size++;
        modCount++;
    }

addFirst(E e)

// 添加到集合的第一个位置
    public void addFirst(E e) {
        linkFirst(e);
    }

    private void linkFirst(E e) {
        final Node f = first;
//前驱为null，后继为当前头节点
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
// 判断linkedList是否为空
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
//linkedList长度加一
        size++;
        modCount++;
    }

addLast(E e)

// 尾部添加
    public void addLast(E e) {
// 在add（）方法已介绍
        linkLast(e);
    }

remove(Object o)

    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;
        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;
// linkedList长度减1；
        size--;
        modCount++;
        return element;
    }

set(int index, E element)

// 将此列表中指定位置的元素替换为指定的元素。
   public E set(int index, E element) {
        checkElementIndex(index);

        Node x = node(index);
//得到要替换元素的值
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
//异常
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
// 判断元素下标是否越界
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

contains(Object o)

// 判断是否包含元素 o 
   public boolean contains(Object o) {
// 返回值 != -1;则包含。
        return indexOf(o) != -1;
    }
// 查找相应元素并返回下标，若没有，返回-1
    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;
    }

get(int index) 

// 返回下标为 index 的元素 
   public E get(int index) {
// 安全检测
        checkElementIndex(index);
        return node(index).item;
    }

size()

// 返回linkedList的长度  
    public int size() {
        return size;
    }

2.linkedList 方法的使用

 

    public static void main(String[] args) {
       linkedList linkedList = new  linkedList<>();
       linkedList.add(1);
       linkedList.add(2);
       linkedList.add(3);
       linkedList.add(4);

       int size = linkedList.size();
       System.out.println("linkedList的个数为："+size);

       System.out.print("操作前的元素为：");
       Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()){
            Integer value=iterator.next();
            System.out.print(value+" ");
        }
        System.out.println("");


        linkedList.remove(Integer.valueOf(1));

        System.out.print("删除后的元素为：");
        Iterator iterator1 = linkedList.iterator();
        while (iterator1.hasNext()){
            Integer value1=iterator1.next();
            System.out.print(value1+" ");
        }
        System.out.println("");


        linkedList.set(1,5); // 2 5 4

        System.out.print("修改后的元素为：");
        Iterator iterator2 = linkedList.iterator();
        while (iterator2.hasNext()){
            Integer value1=iterator2.next();
            System.out.print(value1+" ");
        }
        System.out.println("");


        boolean result = linkedList.contains(Integer.valueOf(2));
        System.out.println(result);

    }