Java集合框架

使用案例(增删改查方法)
实现原理

LinkList

只有后指针时，是单向链表
有前后指针时，是双向链表
后指针变成左右指针时，是二叉树

案例

初始化

LinkedList<String> list = new LinkedList<>();

增

add()

void add(int index, E element)

list.add("星期一");
list.add("星期二");
list.add("星期三");

boolean addAll(Collection c)
此方法会将所有指定集合中的元素添加到此列表的结尾，因为它们是由指定collection的迭代器返回的顺序。
addFirst() 方法将元素添加到第一位；
addLast() 方法将元素添加到末尾。

删

remove()：删除第一个节点
remove(int)：删除指定位置的节点
remove(Object)：删除指定元素的节点
removeFirst()：删除第一个节点
removeLast()：删除最后一个节点

remove 内部调用的是 removeFirst

改

list.set(0, "星期一");

查

可以分为三种：

indexOf(Object)：查找某个元素所在的位置
get(int)：查找某个位置上的元素
int size()
此方法返回此列表中的元素数。

关于indexOf()方法

int lastIndexOf(Object o)
这个方法返回指定元素的最后一个匹配项的索引在此列表中，或者-1，如果此列表中不包含该元素。

关于get()方法

getFirst() 方法用于获取第一个元素；
getLast() 方法用于获取最后一个元素；
poll() 和 pollFirst() 方法用于删除并返回第一个元素（两个方法尽管名字不同，但方法体是完全相同的）；
pollLast() 方法用于删除并返回最后一个元素；
peekFirst() 方法用于返回但不删除第一个元素。

其他

void clear()
此方法删除所有来自此列表中的元素。
boolean contains(Object o)
如果此列表包含指定的元素，此方法返回true

实现原理

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

add方法实现原理

add 方法内部其实调用的是 linkLast 方法，linkLast顾名思义就是在链表的尾部链接元素

public boolean add(E e) {
    linkLast(e);
    return true;
}

remove方法实现原理

remove(int) 内部其实调用的是 unlink 方法。

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

unlink 方法其实很好理解，就是更新当前节点的 next 和 prev，然后把当前节点上的元素设为 null。

/**
 * Unlinks non-null node x.
 */
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;
  }

  x.item = null;
  size--;
  modCount++;
  return element;
}

Java 集合框架LinkedList

Java集合框架

LinkList

案例

初始化

增

删

改

查

其他

实现原理

add方法实现原理

remove方法实现原理