Java面试一天一题（day 7面试题：聊聊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;
    }
}

public boolean add(E e) {
linkLast(e);
return true;    
}
void linkLast(E e) {
//获取最后一个节点
final Node<E> l = last;
//这里创建出一个新的节点，它的前一个节点指向l,要保存的数据即传入进来的数据，后一个节点为null
final Node<E> newNode = new Node<>(l, e, null);
//接着将这个新节点当做链表的最后一个节点保存起来
last = newNode;
//如果刚开始最后一个节点为null，说明是第一次添加
if (l == null)
    first = newNode;
else
    //否则将刚开始最后一个节点的下一个节点的引用指向新创建的节点
    l.next = newNode;
size++;
modCount++;
}
‍

public E get(int index) {
    //参数合法检验
    checkElementIndex(index);
    return node(index).item;
}
//取该节点保存的值并返回
Node<E> node(int index) {
    //index如果小于链表大小的一半，则从头遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //index如果大于等于链表大小的一半，则从尾部遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

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


E unlink(Node<E> x) {
    //分别保存当前要删除节点的值、前置节点、后置节点
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    //前置节点为null，说明当前节点为首节点
    if (prev == null) {
        first = next;
    } else {
        //前置节点不为null，将前置节点的next后移
        prev.next = next;
        x.prev = null;  //(1)
    }
    
    //后置节点为null，说明当前节点为尾节点
    if (next == null) {
        last = prev;
    } else {
        //后置节点不为null，将后置节点的prev指向前置节点
        next.prev = prev;
        x.next = null;  //(2)
    }
    x.item = null;      //(3)
    size--;
    modCount++;
    return element;
}
‍

//以下是for循环遍历
for(int i =0;i<list.size();i++){
  list.get(i);
}
//迭代器遍历
Iterator<String> it = list.listIterator();
while(it.hasNext()){
        System.out.print(it.next()+" ");
}
‍