LinkedList

目录

一、基本结构

// 元素的个数 (链表长度)
transient int size = 0;

// 头结点
transient Node<E> first;

// 尾结点
transient Node<E> last;

//节点类 定义如下
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;
    }
}

从上面源代码可知,底层结构是链表,而且是一个双向链表,这也就意味着不会再有容量的限制,没了扩容操作,但自身不仅仅实现了List相关操作还实现了Deque相关操作,我们以List操作为主

二、add操作

采用尾插法,尾部为空时说明链表为空,新节点会同时成为尾节点和头节点,尾部不为空,就把尾结点指向到新节点,最后链表长度+1

源代码如下:


public boolean add(E e) {
    linkLast(e);
    return true;
}
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;
  // 元素个数+1(链表长度+1)
  size++;
  modCount++;
}

因为是list所以同样可以直接指定位置插入元素,操作也很简单,先找到原来的节点,然后把新节点放进去,改变原节点的上一个指向,总得来说原来的节点下移

源代码如下:

public void add(int index, E element) {
    // 索引校验  不能<0 或者 >链表长度
    checkPositionIndex(index);
    // 判断是否在尾部插入  
    if (index == size)
        // 同上尾插法
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// 找到索引原有位置的节点
Node<E> node(int index) {
    // 判断索引位置是在链表上半部还是在下半部
    if (index < (size >> 1)) {
        // 上半部从头节点开始遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 下半部从尾节点开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
void linkBefore(E e, Node<E> succ) {
    // 获取原节点的上一个节点
    final Node<E> pred = succ.prev;
    // 新建一个节点  原节点下移
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

三、get操作

就是上面说的分半然后遍历

源代码如下:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
// 找到索引原有位置的节点
Node<E> node(int index) {
    // 判断索引位置是在链表上半部还是在下半部
    if (index < (size >> 1)) {
        // 上半部从头节点开始遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 下半部从尾节点开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

四、set操作

找到节点,然后把节点内部的值替换

源代码如下:

public E set(int index, E element) {
    checkElementIndex(index);
    //找到索引对应的节点
    Node<E> x = node(index);
    E oldVal = x.item;
    //把节点对应的值替换
    x.item = element;
    return oldVal;
}

五、contains操作

因为是允许存在null值的,所以遍历的时候要两种情况遍历,一种是遍历null值,一种是对比值,遍历找值对应节点的索引,没找到就返回-1 即false不存在

源代码如下:

public boolean contains(Object o) {
    return indexOf(o) != -1;
}
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        //遍历链表 找null值
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        //遍历链表 
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

六、remove操作

分半查找到元素,然后修改指向

源代码如下:

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

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> 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;
    }
    // 把值置为null 便于GC
    x.item = null;
    // 长度-1
    size--;
    modCount++;
    return element;
}

Last Updated: