[TOC]
# 代碼
~~~
public class LinkedList<E> {
//不需要知道node是怎么實現
private class Node {
//元素
public E e;
//下一個元素的位置
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
//虛擬頭節點
private Node dummyHead;
//大小不允許外部修改
private int size;
public LinkedList() {
//初始是什么都沒有
dummyHead = new Node(null, null);
size = 0;
}
//返回鏈表是否為空
public boolean isEmpty() {
return size == 0;
}
//在鏈表的index(0-based)位置添加新的元素e
//在鏈表中不是一個常用的操作
public void add(int index, E e) {
//index是要插入的位置
if (index < 0 || index > size) {
//這個位置不能是負的,或者比鏈表的最大值要大
throw new IllegalArgumentException("Add failed.Illegal index.");
}
//先把前面一個元素的位置置為虛擬頭元素
Node prev = dummyHead;
//前面一個元素就是index,因為是從dummyHead遍歷的
for (int i = 0; i < index; i++) {
//找到了就賦值給前面一個元素
prev = prev.next;
}
//創建節點
Node node = new Node(e);
//把原來這位置的指向下一個元素拿來給自己
node.next = prev.next;
//前面一個元素的指向下一個就是自己了
prev.next = node;
//可以簡化這一步
// prev.next = new Node(e, prev.next);
//維護下鏈表大小
size++;
}
//在鏈表頭添加新的元素e
public void addFirst(E e) {
add(0, e);
}
//在鏈表末尾添加新的元素e
public void addLast(E e) {
add(size, e);
}
// 獲取鏈表中的元素個數
public int getSize(){
return size;
}
//獲取第index個位置的索引
public E get(int index) {
if (index < 0 || index > size) {
//這個位置不能是負的,或者比鏈表的最大值要大
throw new IllegalArgumentException("Get failed.Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
//獲得鏈表第一個元素
public E getFirst() {
return get(0);
}
//獲得鏈表的最后一個元素
public E getLast() {
return get(size - 1);
}
//修改鏈表中的第index個位置的元素為e
public void set(int index, E e) {
if (index < 0 || index > size) {
//這個位置不能是負的,或者比鏈表的最大值要大
throw new IllegalArgumentException("Update failed.Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
//查找鏈表中是否有元素e
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
//刪除元素
public E remove(int index) {
if (index < 0 || index > size) {
//這個位置不能是負的,或者比鏈表的最大值要大
throw new IllegalArgumentException("Remove failed.Illegal index.");
}
Node prev = this.dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
//要刪除的元素
Node retNode = prev.next;
//把要刪除的下一個節點拼接到上一個節點的后面
prev.next = retNode.next;
//要刪除的元素,被gc
retNode.next = null;
//維護長度
size--;
return retNode.e;
}
//刪除第一個元素,返回刪除的元素
public E removeFirst() {
return remove(0);
}
//從鏈表中刪除最后一個元素,返回刪除的元素
public E removeLast() {
return remove(size - 1);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
~~~
# 測試
~~~
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for (int i = 0; i < 5; i++) {
linkedList.addFirst(i);
System.out.println(linkedList);
}
linkedList.add(2, 666);
System.out.println(linkedList);
linkedList.remove(2);
System.out.println(linkedList);
}
~~~
# 時間復雜度分析
添加操作
~~~
addLast(e) O(n)
addFirst(e) O(1)
add(index,e) O(n/2) = O(n)
~~~
刪除操作
~~~
removeLast(e) O(n)
removeFirst(e) O(1)
remove(index,e) O(n/2)=O(n)
~~~
修改操作
~~~
set(index,e) O(n)
~~~
查找操作
~~~
get(index) O(n)
contains(e) O(n)
~~~
鏈表不適合做修改
