1、數(shù)據(jù)結(jié)構(gòu)
? ? ? ? LinkedList是用雙向鏈表的形式來保存數(shù)據(jù)的抓狭，也是一個(gè)有序結(jié)構(gòu)伯病。其中包含3個(gè)屬性，int size(集合實(shí)際保存的元素個(gè)數(shù))否过，Node<E> first(第一個(gè)節(jié)點(diǎn))午笛，Node<E> last(最后一個(gè)節(jié)點(diǎn))。
2苗桂、線程安全
LinkedList是線程不安全的药磺。
3、常用方法
～煤伟、節(jié)點(diǎn)Node<E>
Node<E>是構(gòu)成雙向鏈表的節(jié)點(diǎn)癌佩，是LinkedList的內(nèi)部類：
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;
? ? }
}
// 在鏈表最前添加
private void linkFirst(E e) {
? ? final Node<E> f =first;
? ? final Node<E> newNode = new Node<>(null, e, f)
? ? first = newNode;
? ? if(f == null)
? ? ? ? last = newNode;
? ? else
? ? ? ? f.prev = newNode;
? ? size++;
? ? modCount++;
}
// 在鏈表最后添加元素
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;
? ? size++;
? ? modCount++;
}
// 在某個(gè)節(jié)點(diǎn)之前添加
void linkBefor(E e, Node<E> succ) {
? ? // 插入位置的前一個(gè)節(jié)點(diǎn)
? ? final Node<E> pred = succ.prev;
? ? // 用插入位置前一個(gè)節(jié)點(diǎn)pred、插入元素e便锨、插入位置本來的節(jié)點(diǎn)succ围辙，作為參數(shù)生成的新節(jié)點(diǎn)
? ? // pred為新節(jié)點(diǎn)的前節(jié)點(diǎn)prev，succ為新節(jié)點(diǎn)的后節(jié)點(diǎn)next
? ? final Node<E> newNode = new Node<>(pred, e, succ);
? ? // 原插入位置的節(jié)點(diǎn)的前節(jié)點(diǎn)指向新節(jié)點(diǎn)
? ? succ.prev = newNode;
? ? if (pred == null)
? ? ? ? first = newNode;
? ? else
? ? ? ? // 前節(jié)點(diǎn)的后節(jié)點(diǎn)指向新節(jié)點(diǎn)
? ? ? ? pred.next = newNode;
? ? size++;
? ? modCount++;
}
～放案、add()? // 在最后添加
public boolean add(E e) {
? ? linkLast(e);
? ? return true;
}
～酌畜、add(int index, E element)? //在指定的index位置添加
public void add(int index, E element) {
? ? // 保證index大于0，小于list.size()
? ? checkPositionIndex(index);
? ? if (index == size)
? ? ? ? // 最后插入卿叽，同add()
? ? ? ? linkLast(element);
? ? else
? ? ? ? // 中間插入桥胞，需要返回index位置的節(jié)點(diǎn)
? ? ? ? linkBefor(element, node(index));
}
// 返回index位置節(jié)點(diǎn)
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;
? ? }
}
～、addFirst(E e)? // 在最前面添加
public void addFirst(E e) {
? ? linkFirst(e);
}
～考婴、addLast(E e)? // 在最后添加
public void addLast(E e) {
? ? linkLast(e);
}
～贩虾、addAll(Collection<? extends E> c)? //在鏈尾添加集合
先將c轉(zhuǎn)為數(shù)組a，再將a中的元素一個(gè)一個(gè)按add()往后添加了
public boolean addAll(Collection<? extends E> c) {
? ? return addAll(size, c)
}
～沥阱、addAll(int index, Collection<? extends E> c)? // 在指定位置添加集合
1缎罢、c轉(zhuǎn)數(shù)組a
2、取原鏈表index位置元素succ和它的前一個(gè)元素pred
3、循環(huán)a取元素o策精，用pred舰始、o、null生成新節(jié)點(diǎn)newNode咽袜。pred.next節(jié)點(diǎn)指向newNode丸卷，newNode賦給pred
4、將循環(huán)玩的最后一個(gè)節(jié)點(diǎn)pred.next指向第二步中的succ询刹，succ.prev指向pred
～谜嫉、get(int index)? // 獲取index位置存放的元素
public E get(int index) {
? ? checkElementIndex(index);
? ? return node(index).item;
}
～、getFirst()凹联，getLast()? // 獲取第一沐兰、最后一個(gè)元素
判斷first，last是否為空蔽挠，不為空return? first.item或last.item
～住闯、set(int index, E element)? 替換index位置的節(jié)點(diǎn)的元素item
public E set(int index, E element) {
? ? checkElementIndex(index);
? ? Node<E> x = node(index);
? ? E oldVal = x.item;
? ? x.item = element;
? ? return oldVal;
}
～、刪除節(jié)點(diǎn)-unlink
// 刪除第一個(gè)節(jié)點(diǎn)
private E unlinkFirst(Node<E> f) {
? ? // 取第一個(gè)節(jié)點(diǎn)的元素item和下一個(gè)節(jié)點(diǎn)next
? ? final E element = f.item;
? ? final Node<E> next = f.next;
? ? // 將取出的第一個(gè)元素給null澳淑，使GC生效
? ? f.item = null;
? ? f.next = null;
? ? // 第一個(gè)節(jié)點(diǎn)后移
? ? first = next;
? ? if ( next == null)
? ? ? ? last = null;
? ? else
? ? ? ? next.prev = null;
? ? size—;
? ? modCount++;
? ? return element;
}
// 刪除最后一個(gè)節(jié)點(diǎn)
private E unlinkLast(Node<E> l) {
? ? final E element = l.item;
? ? final Node<E> prev = l.prev;
? ? l.item = null;
? ? l.prev = null;
? ? last = prev;
? ? if(prev == null)
? ? ? ? first == null;
? ? else
? ? ? ? prev.next = null;
? ? size—;
? ? modCount++;
? ? return element;
}
// 刪除節(jié)點(diǎn)
E unlink(Node<E> x) {
? ? 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;
}
～寞秃、remove()? // 從頭開始刪除一個(gè)元素
public E remove() {
? ? // unlinkFirst
? ? return removeFirst();
}
～、removeFirst偶惠，removeLast? //刪除第一或最后一個(gè)元素
判斷不為空后unlinkFirst或unlinkLast
～、remove(Object o)? //刪除第一次出現(xiàn)的與o相等的元素
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;
}
～朗涩、remove(int index)? //刪除指定位置的元素
public E rmove(int index) {
? ? checkElementIndex(index);
? ? return unlink(node(index));
}
