- LinkedList采用双向链表、双端队列实现,线程不安全
- 举例说明
public class test {
public static void main(String[] args) {
//构造LinkedList对象
LinkedList list = new LinkedList();
for (int i=0 ;i < 10;i++){
//添加数据
list.add(i);
}
System.out.println(list);
}
}
- LinkedList list =newLinkedList();
2. list.add(i);
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//添加元素
public boolean add(E e) {
//看这
linkLast(e);
return true;
}
}
3. linkLast(e);
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { void linkLast(E e) { //得到尾节点,此时为空 final Node<E> l = last; //实例化一个新的节点,存储要添加的数据。此时,pre和next都为null final Node<E> newNode = new Node<>(l, e, null); //尾节点指向这个新创建的节点 last = newNode; //如果l为null(true),头节点指向这个新创建的节点 if (l == null) first = newNode; else l.next = newNode;
<span class="hljs-comment">//元素数量+1 size++; <span class="hljs-comment">//操作数+1 modCount++; }
}
- 删除元素
public class test {
public static void main(String[] args) {
//构造LinkedList对象
LinkedList list = new LinkedList();
for (int i=0 ;i < 2;i++){
//添加数据
list.add(i);
}
System.out.println(list);
//默认删除第一个元素
list.remove();
}
}
- list.remove();
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { public E remove() { return removeFirst(); }
<span class="hljs-function"><span class="hljs-keyword">public E <span class="hljs-title">removeFirst<span class="hljs-params">() { <span class="hljs-comment">//获取第一个节点 <span class="hljs-keyword">final Node<E> f = first; <span class="hljs-keyword">if (f == <span class="hljs-keyword">null) <span class="hljs-keyword">throw <span class="hljs-keyword">new NoSuchElementException(); <span class="hljs-keyword">return unlinkFirst(f); } <span class="hljs-comment">//删除第一个元素 <span class="hljs-function"><span class="hljs-keyword">private E <span class="hljs-title">unlinkFirst<span class="hljs-params">(Node<E> f) { <span class="hljs-comment">// assert f == first && f != null; <span class="hljs-comment">//获取第一个节点中的元素 <span class="hljs-keyword">final E element = f.item; <span class="hljs-comment">//获取第一个节点的下一个node <span class="hljs-keyword">final Node<E> next = f.next; <span class="hljs-comment">//将第一个节点的值置空 f.item = <span class="hljs-keyword">null; <span class="hljs-comment">//将指向下一节点的指针置空 f.next = <span class="hljs-keyword">null; <span class="hljs-comment">// help GC <span class="hljs-comment">//让头节点指向下一个node first = next; <span class="hljs-comment">//如果下一节点不存在,置空尾节点指针。否则让下一节点的prev置空,不向前指向。 <span class="hljs-keyword">if (next == <span class="hljs-keyword">null) last = <span class="hljs-keyword">null; <span class="hljs-keyword">else next.prev = <span class="hljs-keyword">null; <span class="hljs-comment">//元素数量-1 size--; <span class="hljs-comment">//操作数+1 modCount++; <span class="hljs-comment">//返回被删除的数据 <span class="hljs-keyword">return element; }
}
将第一个节点中的next指针、item数据置空,第二个节点pre指针置空,头节点指向下一节点
END