上一篇《數(shù)據(jù)結(jié)構(gòu)與算法（一）：概述》中介紹了數(shù)據(jù)結(jié)構(gòu)的一些基本概念，并分別舉例說(shuō)明了算法的時(shí)間復(fù)雜度和空間復(fù)雜度的求解方法。這一篇主要介紹線性表。

一、基本概念

線性表是具有零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。

線性表的基本特征：

• 第一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)元素；
• 最后一個(gè)數(shù)據(jù)元素沒(méi)有后繼元素；
• 其余每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)元素和一個(gè)后繼元素。

抽象數(shù)據(jù)類(lèi)型：

線性表一般包括插入、刪除、查找等基本操作。其基于泛型的API接口代碼如下：

public interface List<E> {//線性表的大小int size();//判斷線性表是否為空boolean isEmpty();void clear();//添加新元素void add(E element);//在指定位置添加新元素void add(int index, E element);//刪除元素E delete(int index);//獲取元素E get(int index);
}

線性表按物理存儲(chǔ)結(jié)構(gòu)的不同可分為順序表（順序存儲(chǔ)）和鏈表（鏈?zhǔn)酱鎯?chǔ)）：

• 順序表（存儲(chǔ)結(jié)構(gòu)連續(xù)，數(shù)組實(shí)現(xiàn)）
• 鏈表（存儲(chǔ)結(jié)構(gòu)上不連續(xù)，邏輯上連續(xù)）

二、順序表

順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)。線性表采用順序存儲(chǔ)的方式存儲(chǔ)就稱(chēng)之為順序表。

其插入刪除操作如圖所示：

注意：

• 插入操作：移動(dòng)元素時(shí)，要從后往前操作，不能從前往后操作，不然元素會(huì)被覆蓋。
• 刪除操作：移動(dòng)元素時(shí)，要從前往后操作。
  代碼如下：

import java.util.*;
public class SequenceList<E> implements List<E>, Iterable<E> {private static final int DEFAULT_CAPACITY = 10;private int size;private E[] elements;@SuppressWarnings("unchecked")public SequenceList() {size = 0;elements = (E[])new Object[DEFAULT_CAPACITY];}public int size() { return size;}public boolean isEmpty(){ return size == 0;}@SuppressWarnings("unchecked")public void clear(){size = 0;elements = (E[])new Object[DEFAULT_CAPACITY];}public void add(E element){ add(size, element);}//在index插入elementpublic void add(int index, E element){if(size >= elements.length) {throw new RuntimeException("順序表已滿，無(wú)法添加"); }if(index < 0 || index > size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }for(int i=size; i>index; i--) {elements[i] = elements[i - 1];}elements[index] = element;size++;}//刪除元素public E delete(int index){if(isEmpty()) {throw new RuntimeException("順序表為空，無(wú)法刪除"); }if(index < 0 || index >= size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }E result = elements[index];for(int i=index; i<size - 1; i++) {elements[i] = elements[i + 1];}size--;elements[size] = null; //避免對(duì)象游離return result;}public E get(int index){if(index < 0 || index >= size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }return elements[index];}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int num = 0;@Overridepublic E next() {                return elements[num++];}@Overridepublic boolean hasNext() {return num < size;}};}public static void main(String[] args) {SequenceList<Integer> sl = new SequenceList<Integer>();for(int i=0;i<10;i++) {sl.add(i);}System.out.println("刪除1位置元素："+sl.delete(1));sl.add(0,15);for(int i=0;i<sl.size();i++) {System.out.print(sl.get(i)+" ");}}
}

這里需要注意，由于java中不能直接創(chuàng)建泛型數(shù)組，所以在順序表的構(gòu)造函數(shù)中先創(chuàng)建了一個(gè)Object的數(shù)組，然后將它強(qiáng)轉(zhuǎn)為泛型數(shù)組并使用@SuppressWarnings(“unchecked”)消除未受檢的警告。若對(duì)這點(diǎn)還有什么疑問(wèn)可以參考我的學(xué)習(xí)筆記 Effective java筆記（四），泛型 中第25、26條。另外在進(jìn)行刪除操作時(shí)應(yīng)避免對(duì)象游離。

在java中，數(shù)組一旦創(chuàng)建其大小不能改變，所以在上面的實(shí)現(xiàn)中，為了盡可能的不浪費(fèi)內(nèi)存必須事先準(zhǔn)確的預(yù)估順序表的容量。但現(xiàn)實(shí)應(yīng)用中由于存在很多不確定因素，這往往是不切實(shí)際的。這時(shí)可使用動(dòng)態(tài)調(diào)整數(shù)組大小的方法來(lái)解決這個(gè)問(wèn)題。代碼如下：

private void resize(int num){@SuppressWarnings("unchecked")E[] temp = (E[]) new Object[num];for(int i=0; i<size; i++) {temp[i] = elements[i];}elements = temp;
}

然后在插入和刪除操作中分別加入判斷語(yǔ)句，來(lái)調(diào)用這個(gè)方法

//在index插入element
public void add(int index, E element){//當(dāng)順序表滿時(shí)，容量加倍if(size >= elements.length) {// throw new RuntimeException("順序表已滿，無(wú)法添加"); resize(elements.length*2);}if(index < 0 || index > size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }....
}//刪除元素
public E delete(int index){....elements[size] = null;//當(dāng)元素?cái)?shù)量小于容量的1/4時(shí)，容量減半if(size>0 && size <= elements.length/4) {resize(elements.length/2);}return result;
}

**注意：**在刪除操作中檢查條件為「順序表的大小是否小于容量的 1/4」，而不是1/2。這樣可以避免在1/2這個(gè)零界點(diǎn)處反復(fù)進(jìn)行插入刪除操作時(shí)，數(shù)組進(jìn)行頻繁復(fù)制。

順序表效率分析：

• 順序表插入和刪除一個(gè)元素，最好情況下其時(shí)間復(fù)雜度（這個(gè)元素在最后一個(gè)位置）為O(1)，最壞情況下其時(shí)間復(fù)雜度為O(n)。
• 順序表支持隨機(jī)訪問(wèn)，讀取一個(gè)元素的時(shí)間復(fù)雜度為O(1)。

順序表的優(yōu)缺點(diǎn)：

• 優(yōu)點(diǎn)：支持隨機(jī)訪問(wèn)
• 缺點(diǎn)：插入和刪除操作需要移動(dòng)大量的元素，造成存儲(chǔ)空間的碎片。
  順序表適合元素個(gè)數(shù)變化不大，且更多是讀取數(shù)據(jù)的場(chǎng)合。

三、鏈表

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

鏈表根據(jù)構(gòu)造方式的不同可以分為：

• 單向鏈表
• 單向循環(huán)鏈表
• 雙向鏈表

1、單向鏈表

單鏈表有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種結(jié)構(gòu)，其結(jié)構(gòu)如下

在帶頭結(jié)點(diǎn)的單鏈表中，其第一個(gè)結(jié)點(diǎn)被稱(chēng)作頭結(jié)點(diǎn)。第一個(gè)存放數(shù)據(jù)元素的結(jié)點(diǎn)稱(chēng)作首元結(jié)點(diǎn)，頭結(jié)點(diǎn)指向首元結(jié)點(diǎn)。頭結(jié)點(diǎn)是為了操作的統(tǒng)一與方便而設(shè)立的，其一般不放數(shù)據(jù)（也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等）。此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。

帶頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn):

• 在鏈表第一個(gè)位置上進(jìn)行的操作（插入、刪除）和其它位置上的操作一致,無(wú)須進(jìn)行特殊處理;
• 無(wú)論鏈表是否為空，head一定不為空，這使得空表和非空表的處理一致。

由于帶頭結(jié)點(diǎn)的鏈表更容易操作，這里僅實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表

帶頭結(jié)點(diǎn)的鏈表插入與刪除示意圖：

代碼如下：

import java.util.*;
public class LinkedList<E> implements List<E>, Iterable<E>{private Node head;private int size;private class Node {E element;Node next;}LinkedList() {head = new Node();}@Override public int size() { return size;}@Override public boolean isEmpty() { return size==0;}@Override public void clear() {head = new Node();size = 0;}@Override public void add(E element) {add(0, element);}@Override public void add(int index, E element) {if(index < 0 || index > size)throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤");Node current = location(index);Node newNode = new Node();newNode.element = element;        Node node = current.next;current.next = newNode;newNode.next = node;size++;}//找到第index個(gè)結(jié)點(diǎn)前的結(jié)點(diǎn)private Node location(int index){Node current = head;for(int i=0; i<index; i++) {current = current.next;}return current;}@Override public E get(int index) {if(index < 0 || index >= size)throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤");return location(index + 1).element;}//刪除第index個(gè)元素@Override public E delete(int index) {if(index < 0 || index >= size)throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤");Node current = location(index);E element = current.next.element;current.next = current.next.next;size--;return element;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node current = head;@Overridepublic E next() {  current = current.next;              return current.element;}@Overridepublic boolean hasNext() {return current.next != null;}};}public static void main(String[] args) throws Exception{LinkedList<Integer> list = new LinkedList<Integer>();for(int i=0;i<10;i++) {list.add(i);}System.out.println("刪除0位置元素："+list.delete(0));list.add(0,15);for (Integer ele : list ) {System.out.print(ele + " ");}}
}

單鏈表效率分析：

在單鏈表上插入和刪除數(shù)據(jù)時(shí)，首先需要找出插入或刪除元素的位置。對(duì)于單鏈表其查找操作的時(shí)間復(fù)雜度為 O(n)，所以

鏈表插入和刪除操作的時(shí)間復(fù)雜度均為 O(n)

鏈表讀取操作的時(shí)間復(fù)雜度為 O(n)

單鏈表優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：不需要預(yù)先給出數(shù)據(jù)元素的最大個(gè)數(shù)，單鏈表插入和刪除操作不需要移動(dòng)數(shù)據(jù)元素
缺點(diǎn)：不支持隨機(jī)讀取，讀取操作的時(shí)間復(fù)雜度為 O(n)。

2、單向循環(huán)鏈表

將單鏈表中終端結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使整個(gè)單鏈表形成一個(gè)環(huán)，這種頭尾相接的單鏈表稱(chēng)為單循環(huán)鏈表，簡(jiǎn)稱(chēng)循環(huán)鏈表。

對(duì)于循環(huán)鏈表，為了使空鏈表與非空鏈表處理一致，通常設(shè)一個(gè)頭結(jié)點(diǎn)。如下圖：

循環(huán)鏈表和單鏈表的主要差異在于鏈表結(jié)束的判斷條件不同，單鏈表為current.next是否為空，而循環(huán)鏈表為current.next不等于頭結(jié)點(diǎn)。對(duì)于循環(huán)鏈表的增刪改查操作與單鏈表基本相同，僅僅需要將鏈表結(jié)束的條件變成current.next != head即可，這里就不在給出了。

在單鏈表中，我們有了頭結(jié)點(diǎn)時(shí)，對(duì)于最后一個(gè)結(jié)點(diǎn)的訪問(wèn)需要 O(n)的時(shí)間，因?yàn)槲覀冃枰獙捂湵砣勘闅v一次。哪有沒(méi)有可能用 O(1)的時(shí)間訪問(wèn)到終端結(jié)點(diǎn)呢？當(dāng)然可以，我們只需改造一下單鏈表，使用指向終端結(jié)點(diǎn)的尾指針來(lái)表示循環(huán)鏈表，這時(shí)訪問(wèn)開(kāi)始結(jié)點(diǎn)（不是頭結(jié)點(diǎn)）和終端結(jié)點(diǎn)的操作都為 O(1)。它們的訪問(wèn)操作分別為end.next.next和end，其中end為指向終端結(jié)點(diǎn)的引用。這個(gè)設(shè)計(jì)對(duì)兩個(gè)循環(huán)鏈表的合并特別有用，可以避免遍歷鏈表的時(shí)間消耗。如：

合并兩個(gè)循環(huán)鏈表的代碼:

public Node merge(Node endA, Node endB) {Node headA = endA.next; //保存A表的頭結(jié)點(diǎn)endA.next = endB.next.next;endB.next = headA;return endB;
}

3、雙向鏈表

雙向鏈表是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。使得兩個(gè)指針域一個(gè)指向其前驅(qū)結(jié)點(diǎn)，一個(gè)指向其后繼結(jié)點(diǎn)。

雙向鏈表的結(jié)點(diǎn)表示：

private class Node {E element;Node prior; //指向前驅(qū)Node next;
}

對(duì)于雙向鏈表，其空和非空結(jié)構(gòu)如下圖：

雙向鏈表是單鏈表擴(kuò)展出來(lái)的結(jié)構(gòu)，它可以反向遍歷、查找元素，它的很多操作和單鏈表相同，比如求長(zhǎng)度size()、查找元素get()。這些操作只涉及一個(gè)方向的指針即可。插入和刪除操作時(shí)，需要更改兩個(gè)指針變量。

插入操作：注意操作順序

在current后插入element的代碼為：

element.prior = current;
element.next = current.next;
current.next.prior = element;
current.next = element;

刪除操作相對(duì)比較簡(jiǎn)單，刪除current結(jié)點(diǎn)的代碼為：

current.prior.next = current.next;
current.next.prior = current.prior;
current = null;

雙向鏈表相對(duì)于單鏈表來(lái)說(shuō)占用了更多的空間，但由于其良好的對(duì)稱(chēng)性，使得能夠方便的訪問(wèn)某個(gè)結(jié)點(diǎn)的前后結(jié)點(diǎn)，提高了算法的時(shí)間性能。是用空間換時(shí)間的一個(gè)典型應(yīng)用。

4、靜態(tài)鏈表

用數(shù)組描述的鏈表叫靜態(tài)鏈表，它是那些沒(méi)有指針和引用的語(yǔ)言，如Basic、Fortran等，實(shí)現(xiàn)鏈表的方式。由于現(xiàn)在的高級(jí)程序語(yǔ)言，一般都擁有指針或引用，可以使用更靈活的指針或引用來(lái)實(shí)現(xiàn)動(dòng)態(tài)鏈表，所以對(duì)于靜態(tài)鏈表僅掌握其算法思想即可。

靜態(tài)鏈表的思想：

• 讓數(shù)組的每個(gè)元素有兩個(gè)數(shù)據(jù)域data和cur組成，其中data用來(lái)存放數(shù)據(jù)元素，cur用來(lái)存放元素的后繼在數(shù)組中的下標(biāo)。我們把cur稱(chēng)為游標(biāo)。

• 通常把數(shù)組中未被使用的位置稱(chēng)為備用鏈表，而數(shù)組的第一個(gè)位置（下標(biāo)為0的位置）的cur存放備用鏈表的第一個(gè)結(jié)點(diǎn)的下標(biāo)；數(shù)組的最后一個(gè)位置的cur則存放第一個(gè)有元素的位置的下標(biāo)，相當(dāng)于鏈表的頭結(jié)點(diǎn)作用。

靜態(tài)鏈表狀態(tài)圖：

代碼如下：

import java.util.*;
public class StaticList<E> implements List<E>, Iterable<E> {private static final int DEFAULT_CAPACITY = 100;private int size;private Node[] nodes;private class Node {E element;int cur;}public StaticList() {initList();}@SuppressWarnings("unchecked")private void initList() {size = 0;//注意這句，不能直接new Node[DEFAULT_CAPACITY]，java不允許創(chuàng)建泛型數(shù)組nodes = new StaticList.Node[DEFAULT_CAPACITY]; for(int i=0; i<nodes.length; i++) {nodes[i] = new Node();nodes[i].cur = i + 1;}nodes[nodes.length - 1].cur = 0;}public int size() { return size;}public boolean isEmpty(){ return size == 0;}public void clear(){initList();}public void add(E element){ add(0, element);}//在index插入elementpublic void add(int index, E element){if(index < 0 || index > size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }Node prior = location(index);int newCur = malloc();if(newCur == 0) {throw new RuntimeException("順序表已滿，無(wú)法添加");}nodes[newCur].element = element;nodes[newCur].cur = prior.cur;prior.cur = newCur;size++;}//找到第index個(gè)結(jié)點(diǎn)前的結(jié)點(diǎn)private Node location(int index){Node prior = nodes[nodes.length - 1];for(int i=0; i<index; i++) {prior = nodes[prior.cur];}return prior;}//分配空間，若備用鏈表非空，返回分配的結(jié)點(diǎn)的下標(biāo)，否則返回0private int malloc() {int i = nodes[0].cur;if(i != 0) {nodes[0].cur = nodes[i].cur; //備用鏈表的下一個(gè)位置}return i;}//將下標(biāo)為k的空閑結(jié)點(diǎn)回收到備用鏈表private void free(int index) {nodes[index].cur = nodes[0].cur;nodes[0].cur = index;}//刪除元素public E delete(int index){if(isEmpty()) {throw new RuntimeException("順序表為空，無(wú)法刪除"); }if(index < 0 || index >= size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }Node prior = location(index);int temp = prior.cur; //要?jiǎng)h除元素的下標(biāo)prior.cur = nodes[temp].cur;E result = nodes[temp].element;nodes[temp].element = null;size--;free(temp);return result;}public E get(int index){if(index < 0 || index >= size) {throw new IndexOutOfBoundsException("參數(shù)輸入錯(cuò)誤"); }return location(index + 1).element;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int temp = nodes[nodes.length - 1].cur;@Overridepublic E next(){  E result = nodes[temp].element;  temp = nodes[temp].cur;          return result;}@Overridepublic boolean hasNext() {return temp != 0;}};}//測(cè)試public static void main(String[] args){StaticList<Integer> sl = new StaticList<Integer>();for(int i=0;i<10;i++) {sl.add(i);}System.out.println("刪除1位置元素："+sl.delete(1));sl.add(1,15);for(int i=0;i<sl.size();i++) {System.out.print(sl.get(i)+" ");}}
}

為了實(shí)現(xiàn)數(shù)組空間的循環(huán)利用，靜態(tài)鏈表將所有未被使用過(guò)的及已經(jīng)被刪除的元素空間用游標(biāo)鏈成一個(gè)備用的鏈表。每當(dāng)插入時(shí)就從備用鏈表上取第一個(gè)結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)，刪除時(shí)將結(jié)點(diǎn)回收到備用鏈表中。上面代碼中的malloc()和free()方法分別對(duì)應(yīng)了這兩種操作。靜態(tài)鏈表的插入和刪除等操作和單鏈表類(lèi)似，僅需注意結(jié)點(diǎn)的cur為一個(gè)int變量，具體操作可以參考上面的代碼。

另外需要注意：靜態(tài)鏈表初始化時(shí)需要?jiǎng)?chuàng)建一個(gè)內(nèi)部類(lèi)泛型數(shù)組StaticList.Node[ ]，我們都知道，java中不能創(chuàng)建泛型數(shù)組，一種解決方案是先創(chuàng)建一個(gè)Object類(lèi)型的數(shù)組，然后再?gòu)?qiáng)轉(zhuǎn)為需要的類(lèi)型。如：

nodes = (Node[])new Object[DEFAULT_CAPACITY]; 

但是在上面的代碼中，使用這種方法運(yùn)行時(shí)會(huì)報(bào)ClassCastException，解決方法是

nodes = new StaticList.Node[DEFAULT_CAPACITY];

這樣就可以解決這個(gè)問(wèn)題，剩下一個(gè)未受檢的警告使用@SuppressWarnings(“unchecked”)注解消除即可。

靜態(tài)鏈表有優(yōu)缺點(diǎn)：

• 優(yōu)點(diǎn)：插入刪除操作時(shí)，只需要修改游標(biāo)，無(wú)需移動(dòng)元素

• 缺點(diǎn)：需要事先預(yù)估鏈表的容量；不能隨機(jī)讀取元素；需要人為的管理數(shù)組的分配（類(lèi)似于管理內(nèi)存分配），失去了java語(yǔ)言的優(yōu)點(diǎn)。

總的來(lái)說(shuō)，靜態(tài)鏈表是為沒(méi)有指針的語(yǔ)言設(shè)計(jì)的一種實(shí)現(xiàn)鏈表的方法，盡管可能用不上，但掌握其設(shè)計(jì)思想還是很有必要的。

總結(jié)一下，這節(jié)主要介紹了線性表兩種不同結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）的實(shí)現(xiàn)方法，它們是其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，也是現(xiàn)在企業(yè)面試中最?？嫉臄?shù)據(jù)結(jié)構(gòu)類(lèi)型之一。