前面兩節(jié)課程主要介紹了動態(tài)數(shù)組姨拥、棧以及隊列這樣三種數(shù)據(jù)結(jié)構(gòu)炊甲，這三種數(shù)據(jù)結(jié)構(gòu)的底層都是依托于靜態(tài)數(shù)組構(gòu)建的亮瓷，靠resize解決固定容量的問題。本節(jié)課介紹一種真正的動態(tài)數(shù)據(jù)結(jié)構(gòu)-鏈表晰甚，鏈表也是一種線性數(shù)據(jù)結(jié)構(gòu)衙传，是最簡單的動態(tài)數(shù)據(jù)結(jié)構(gòu)。
1. 鏈表基礎(chǔ)
1.1 鏈表的特點
-
鏈表的數(shù)據(jù)存儲在節(jié)點(Node)中厕九，節(jié)點中還包含下一節(jié)點的地址
class Node{ E e; Node next; }
LinkedList.png
前面講到蓖捶，數(shù)組最好用于索引有語意的情形，其最大的優(yōu)點是支持快速查詢
而與數(shù)組相比扁远，鏈表的優(yōu)點是它是一種真正的動態(tài)結(jié)構(gòu)俊鱼，不需要處理固定容量的問題刻像；缺點則是喪失了隨機(jī)訪問的能力
-
鏈表的基本結(jié)構(gòu)(支持泛型)：
public class LinkedList<E> { // 私有節(jié)點（Node）類 private class Node{ private E e; private 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 head; // 頭節(jié)點 private int size; // 鏈表當(dāng)前所存節(jié)點數(shù) public LinkedList() { head = new Node(); size = 0; } // 獲取鏈表中的元素個數(shù) public int getSize(){ return size; } // 返回鏈表是否為空 public boolean isEmpty() { return size == 0; } }
1.2 添加元素
LinkedList.png
鏈表中添加元素分為兩種情況：
-
一種是向鏈表頭添加元素
AddHead.png
此時需要將鏈表頭(head)作為待添加元素node的下一節(jié)點：node.next = head
node.next=head
然后將node賦為新的head節(jié)點：head = node;
head=node// 在鏈表頭添加新的元素e public void addFirst(E e){ Node node = new Node(e,null); node.next = head; head = node; // head = new Node(e,head); size ++; } -
一種是向鏈表中間添加元素
例如將node 添加到索引位置為2的位置（非典型應(yīng)用，鏈表中一般不討論索引的概念）并闲，關(guān)鍵點在于定義一個prev節(jié)點细睡，指向待添加位置的前一個節(jié)點
initPrev
prev
找到prev之后，將prev的下一節(jié)點賦為node的下一節(jié)點: node.next = prev.next
node.next=prev.next
然后將node賦為prev的下一節(jié)點：prev.next = node
prev.next = node// 在鏈表的index（0-based）位置添加新的元素e // 非常規(guī)方法 public void add(int index,E e) { if(index<0 || index >=size) throw new IllegalArgumentException("Add failed. Index is illegal. "); if (index == 0) { Node node = new Node(e); node.next = head; head = node; } else { // 從鏈表頭開始帝火，找到索引位置的前一位 Node pre = head; for(int i=0;i<index - 1;i++) { pre = pre.next; } Node newNode = new Node(e); newNode.next = pre.next; pre.next = newNode; // pre.next = new Node(e,pre.next); size ++; } } -
上述實現(xiàn)方法纹冤，如果在頭節(jié)點插入元素，要采取特殊處理购公，為了避免插入邏輯的不同，可以為鏈表設(shè)立虛擬頭節(jié)點：
dummyHead// 設(shè)立虛擬頭節(jié)點的鏈表 public class LinkedList<E> { private class Node{ private E e; private 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;// 虛擬頭節(jié)點雁歌，不存儲任何數(shù)據(jù) private int size; public LinkedList() { dummyHead = new Node(); size = 0; } // 獲取鏈表中的元素個數(shù) public int getSize(){ return size; } // 返回鏈表是否為空 public boolean isEmpty() { return size == 0; } // 在鏈表的index（0-based）位置添加新的元素e // 使用虛擬鏈表頭宏浩，可以不單獨處理鏈表頭的插入操作 public void add(int index,E e) { if(index<0 || index >size) throw new IllegalArgumentException("Add failed. Index is illegal. "); // 從虛擬鏈表頭開始，找到索引位置的前一位 Node pre = dummyHead; for(int i=0;i<index;i++) { pre = pre.next; } Node newNode = new Node(e); newNode.next = pre.next; pre.next = newNode; // pre.next = new Node(e,pre.next); size ++; } // 在鏈表頭插入新元素e public void addFirst(E e) { add(0,e); } // 在鏈表尾添加新元素e public void addLast(E e) { add(size,e); } }
1.3 鏈表的遍歷靠瞎、查詢和修改
-
在鏈表中查找元素
從頭節(jié)點開始比庄，遍歷整個鏈表，依次對比乏盐，找到后返回真佳窑，找不到則返回假：// 在鏈表中查找元素 public boolean contains(E e) { Node cur = dummyHead.next; while(cur!=null) { if(cur.e.equals(e)) return true; cur = cur.next; } return false; } -
獲取鏈表中指定索引位置的元素
非典型應(yīng)用：// 獲得鏈表的第index(0-based)個位置的元素 public E get(int index) { if(index<0 || index >=size) throw new IllegalArgumentException("Get failed. Index is illegal. "); 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（0-based）個位置的元素為e public void set(int index,E e) { if(index<0 || index >=size) throw new IllegalArgumentException("Set failed. Index is illegal. "); Node cur = dummyHead.next; for(int i=0;i<index;i++) { cur = cur.next; } cur.e = e; }
1.4 鏈表元素的刪除
-
刪除索引為2位置的元素
找到指定索引位置的前一節(jié)點prev：
Prev
Prev2
Prev3
將prev的下一節(jié)點賦為delNode的下一節(jié)點：prev.next = delNode.next
prev.next = delNode.next
將待刪除節(jié)點delNode的下一節(jié)點置為空：delNode.next = null
delNode.next = null// 從鏈表中刪除元素e public void removeElement(E e) { Node pre = dummyHead; // 從虛擬頭節(jié)點出發(fā)，找到待刪除元素的前一節(jié)點 while(pre.next!=null) { if(pre.next.e.equals(e)) break; pre = pre.next; } // 如果找到的前一節(jié)點不是最后一個元素父能，則執(zhí)行刪除操作 if(pre.next!=null) { Node delNode = pre.next; pre.next = delNode.next; delNode.next = null; size --; } // 如果找到最后元素神凑，還沒有找到元素e else { // throw new IllegalArgumentException("Remove failed. The element is not included in list."); } }
2. 使用鏈表實現(xiàn)棧
2.1 鏈表的時間復(fù)雜度分析
- 添加操作：
| 函數(shù)名 | 描述 | 時間復(fù)雜度 |
|---|---|---|
| addLast(e) | 在鏈表尾節(jié)點后添加元素，需要遍歷整個鏈表 | |
| addFirst(e) | 在鏈表頭節(jié)點前添加元素何吝，只需一步操作 | |
| add(index,e) | 在指定索引位置添加元素溉委，計算復(fù)雜度期望值 |
- 刪除操作
| 函數(shù)名 | 描述 | 時間復(fù)雜度 |
|---|---|---|
| removeLast(e) | 刪除鏈表尾節(jié)點，需要遍歷整個鏈表 | |
| removeFirst(e) | 刪除鏈表頭節(jié)點爱榕，只需一步操作 | |
| remove(index,e) | 刪除指定索引位置的節(jié)點瓣喊，計算復(fù)雜度期望值 |
- 修改與查找
| 函數(shù)名 | 描述 | 時間復(fù)雜度 |
|---|---|---|
| set(index,e) | 修改指定索引位置的節(jié)點，計算復(fù)雜度期望值 | |
| get(index) | 獲取指定索引位置的節(jié)點元素黔酥，同上 | |
| contains(e) | 判斷鏈表中是否存在指定元素藻三，遍歷整個鏈表 |
仔細(xì)觀察鏈表的增刪改查操作，如果只對鏈表頭節(jié)點進(jìn)行增刪操作跪者，其復(fù)雜度均為棵帽；而修改操作并非常規(guī)操作；查找操作如果只查找頭節(jié)點坑夯，時間復(fù)雜度也為
岖寞，因此鏈表的一個典型應(yīng)用就是實現(xiàn)棧（在同一端增加和刪除）。
回顧棧的幾個功能函數(shù)：
- pop() 彈棧
- push() 壓棧
- isEmpty() 判斷棧是否為空
- getSize() 棧內(nèi)元素個數(shù)
- peek() 查看棧頂元素
2.2 棧接口
public interface Stack<E> {
int getSize();
boolean isEmpty();
E peek();
E pop();
void push(E e);
}
2.3 鏈表數(shù)據(jù)結(jié)構(gòu)類
public class LinkedList<E> {
private class Node{
private E e;
private 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();
size = 0;
}
// 獲取鏈表中的元素個數(shù)
public int getSize(){
return size;
}
// 返回鏈表是否為空
public boolean isEmpty() {
return size == 0;
}
// 在鏈表的index（0-based）位置添加新的元素e
// 使用虛擬鏈表頭柜蜈，可以不單獨處理鏈表頭的插入操作
public void add(int index,E e) {
if(index<0 || index >size)
throw new IllegalArgumentException("Add failed. Index is illegal. ");
// 從虛擬鏈表頭開始仗谆，找到索引位置的前一位
Node pre = dummyHead;
for(int i=0;i<index;i++) {
pre = pre.next;
}
Node newNode = new Node(e);
newNode.next = pre.next;
pre.next = newNode;
// pre.next = new Node(e,pre.next);
size ++;
}
// 在鏈表頭插入新元素e
public void addFirst(E e) {
add(0,e);
}
// 在鏈表尾添加新元素e
public void addLast(E e) {
add(size,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;
}
// 獲得鏈表的第index(0-based)個位置的元素
public E get(int index) {
if(index<0 || index >=size)
throw new IllegalArgumentException("Get failed. Index is illegal. ");
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（0-based）個位置的元素為e
public void set(int index,E e) {
if(index<0 || index >=size)
throw new IllegalArgumentException("Set failed. Index is illegal. ");
Node cur = dummyHead.next;
for(int i=0;i<index;i++) {
cur = cur.next;
}
cur.e = e;
}
// 從鏈表中刪除index(0-based)位置的元素, 返回刪除的元素
public E remove(int index) {
if(index<0 || index >=size)
throw new IllegalArgumentException("Set failed. Index is illegal. ");
// 從虛擬鏈表頭開始指巡，找到索引前一位的結(jié)點
Node pre = dummyHead;
for(int i = 0;i<index;i++) {
pre = pre.next;
}
Node cur = pre.next;
pre.next = cur.next;
cur.next = null;
size--;
return cur.e;
}
// 從鏈表刪除第一個元素，返回刪除的元素
public E removeFirst() {
return remove(0);
}
// 刪除鏈表尾的元素隶垮，返回刪除的元素
public E removeLast() {
return remove(size-1);
}
// 從鏈表中刪除元素e
public void removeElement(E e) {
Node pre = dummyHead;
while(pre.next!=null) {
if(pre.next.e.equals(e))
break;
pre = pre.next;
}
if(pre.next!=null) {
Node delNode = pre.next;
pre.next = delNode.next;
delNode.next = null;
size --;
}
else {
// throw new IllegalArgumentException("Remove failed. The element is not included in list.");
}
}
@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();
}
}
2.4 基于鏈表的棧數(shù)據(jù)結(jié)構(gòu)
public class LinkedListStack<E> implements Stack<E> {
// 私有成員變量LinkedList用來存儲棧元素
private LinkedList<E> list;
public LinkedListStack() {
list = new LinkedList<E>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E e) {
list.addFirst(e);
}
@Override
public E pop() {
return list.removeFirst();
}
@Override
public E peek() {
return list.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: Top ");
res.append(list);
return res.toString();
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
for(int i = 0;i<5;i++
stack.push(i);
System.out.println(stack);
// Stack: Top 0-->NULL
// Stack: Top 1-->0-->NULL
// Stack: Top 2-->1-->0-->NULL
// Stack: Top 3-->2-->1-->0-->NULL
// Top 4-->3-->2-->1-->0-->NULL
}
stack.pop();
System.out.println(stack);
// Stack: Top 3-->2-->1-->0-->NULL
}
}
2.5 數(shù)組棧與鏈表棧實現(xiàn)效率對比
import java.util.Random;
public class Main {
public static double costTime(Stack<Integer> stack,int nCount) {
Random random = new Random();
long startTime = System.nanoTime();
for(int i = 0;i<nCount;i++) {
stack.push(random.nextInt(Integer.MAX_VALUE));
}
for(int i = 0;i<nCount;i++) {
stack.pop();
}
long endTime = System.nanoTime();
return (endTime-startTime) / 1000000000.0 ;
}
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
for(int i = 0;i<5;i++) {
stack.push(i);
System.out.println(stack);
// Stack: [0] top
// Stack: [0,1] top
// Stack: [0,1,2] top
// Stack: [0,1,2,3] top
// Stack: [0,1,2,3,4] top
}
stack.pop();
System.out.println(stack);
// Stack: [0,1,2,3] top
int nCount = 100000;
ArrayStack<Integer> arraystack = new ArrayStack<>();
LinkedListStack<Integer> linkedstack = new LinkedListStack<>();
System.out.println("ArrayStack:"+costTime(arraystack,nCount)); // 0.077
System.out.println("LinkedListStack:"+costTime(linkedstack,nCount)); // 0.036
}
}
可以看到使用鏈表實現(xiàn)棧和使用數(shù)組實現(xiàn)棧藻雪，兩者之間的效率是一致的，這與前一節(jié)的時間復(fù)雜度分析相互映證狸吞。
stack
3. 使用鏈表實現(xiàn)隊列
隊列的特征是一端進(jìn)勉耀，另一端出，因此上述鏈表結(jié)構(gòu)并不適合用來實現(xiàn)隊列蹋偏，需要對結(jié)構(gòu)進(jìn)行一定的改進(jìn)便斥。
對上述鏈表結(jié)構(gòu)增加一個tail標(biāo)簽來標(biāo)記尾節(jié)點的位置，從head和tail端增加元素威始，都只需要一步操作：
- head端: head = new Node(e,head)
- tail端：tail.next = new Node(e); tail = tail.next;
而刪除操作：
- head端(一步操作)：head = head.next;
- tail端：遍歷整個鏈表找到前一節(jié)點prev
因此枢纠，使用改進(jìn)后的鏈表結(jié)構(gòu)實現(xiàn)隊列，從head端出隊黎棠，tail端進(jìn)隊：
LinkedQueue
3.1 隊列接口
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E getFront();
E dequeue();
}
3.2 私有節(jié)點類
private class Node{
private E e;
private Node next;
public Node(E e,Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this.e = e;
next = null;
}
public Node() {
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
3.3 鏈表隊列
public class LinkedListQueue<E> implements Queue<E> {
private int size;
private Node head; // 頭節(jié)點晋渺，出隊
private Node tail; // 尾節(jié)點，入隊
public LinkedListQueue() {
head = new Node();
tail = new Node();
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
// 從tail端入隊
public void enqueue(E e) {
// 如果隊列為空脓斩，head木西，tail均指向第一個入隊元素
if(isEmpty()) {
tail = new Node(e);
head = tail;
}
// 隊列不為空，則添加到尾節(jié)點随静，并維護(hù)tail指向
else {
tail.next = new Node(e);
tail = tail.next;
}
size ++;
}
@Override
// 從head端出隊,返回出隊元素
public E dequeue() {
// 若隊列為空八千，拋異常
if(isEmpty())
throw new IllegalArgumentException("dequeue Failed. The queue is empty.");
// 隊列不為空，刪除頭節(jié)點挪挤，維護(hù)head指向
Node delNode = head;
head = head.next;
// 刪除后叼丑，若隊列為空，維護(hù)tail指向（若不維護(hù)扛门，tail仍指向待刪除元素）
if(head == null) {
tail = null;
}
delNode.next = null;
size --;
return delNode.e;
}
@Override
public E getFront() {
if(isEmpty())
throw new IllegalArgumentException("Get Failed. The queue is empty.");
return head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: head ");
Node cur = head;
while(cur != null) {
res.append(cur.e+"<-");
cur = cur.next;
}
res.append("tail");
return res.toString();
}
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0;i<10;i++) {
queue.enqueue(i);
System.out.println(queue);
if(i%3==2) {
queue.dequeue();
System.out.println(queue);
// Queue: head 0<-tail
// Queue: head 0<-1<-tail
// Queue: head 0<-1<-2<-tail
// Queue: head 1<-2<-tail
// Queue: head 1<-2<-3<-tail
// Queue: head 1<-2<-3<-4<-tail
// Queue: head 1<-2<-3<-4<-5<-tail
// Queue: head 2<-3<-4<-5<-tail
// Queue: head 2<-3<-4<-5<-6<-tail
// Queue: head 2<-3<-4<-5<-6<-7<-tail
// Queue: head 2<-3<-4<-5<-6<-7<-8<-tail
// Queue: head 3<-4<-5<-6<-7<-8<-tail
// Queue: head 3<-4<-5<-6<-7<-8<-9<-tail
}
}
}
}
4. 總結(jié)
本節(jié)課主要學(xué)習(xí)了具有真正的動態(tài)數(shù)據(jù)結(jié)構(gòu)的鏈表鸠信，鏈表是最簡單的動態(tài)數(shù)據(jù)結(jié)構(gòu)，其主要特點是不需要處理固定容量的問題论寨。課程首先分析了鏈表的結(jié)構(gòu)特性星立，然后依次實現(xiàn)了鏈表的增刪改查操作。結(jié)合鏈表的時間復(fù)雜度分析結(jié)果葬凳，使用鏈表實現(xiàn)了前一節(jié)介紹的棧結(jié)構(gòu)绰垂，并進(jìn)一步改進(jìn)鏈表結(jié)構(gòu)，實現(xiàn)了隊列功能火焰。關(guān)于鏈表劲装，還有雙向鏈表等一些特殊的結(jié)構(gòu)，這里暫不討論，目前主要的工作是拓展學(xué)習(xí)的廣度占业，后續(xù)用到時再進(jìn)一步深度研究绒怨。
