基本概念
鏈表和數組類似，但相比于數組，鏈表有動態(tài)大小渡蜻。而且插入和刪除的效率很高，只要O(1)的時間弄痹。但是鏈表的遍歷效率并不高。
Java中嵌器，鏈表為LinkedList類肛真，每個節(jié)點由內置靜態(tài)類Node實現：
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;
}
}
這種鏈表為雙向鏈表，每個節(jié)點儲存它前面的節(jié)點爽航，后面的節(jié)點蚓让，以及它自身的值。也可以去掉節(jié)點的prev屬性讥珍，變?yōu)閱蜗蜴湵怼?/p>
基本操作
Java中LinkedList類的方法历极。
LinkedList<Integer> l = new LinkedList<>();
l.size(); // 鏈表的長度
l.get(); // 返回鏈表某個位置的元素
l.add(); // 向鏈表某個位置添加元素
l.addFirst(); // 向鏈表頭添加元素
l.addLast(); // 向鏈表尾添加元素
l.remove(); // 刪除鏈表某個位置的元素
Lintcode相關題目
- 遍歷
Convert Linked List to Array List
Convert Array List to Linked List
Count Linked List Nodes - 反轉
Reverse Linked List
Reverse Linked List II
Reverse Nodes in K Group - 合并
Merge Two Sorted Lists
Merge k Sorted Lists - 遞歸
Linked List Weighted Sum in Reverse Order
Reverse Order Storage - 其他
Copy List with Random Pointer
Linked List Cycle
Linked List Cycle II
