Java數(shù)據(jù)結(jié)構之線性表

更新時間：2017年03月10日 10:19:19 作者：朝向遠方

線性表是其組成元素間具有線性關系的一種數(shù)據(jù)結(jié)構，對線性表的基本操作主要有，獲取元素，設置元素值，遍歷，插入，刪除，查找，替換，排序等。而線性表可以采用順序儲存結(jié)構和鏈式儲存結(jié)構，本節(jié)主要講解順序表、單鏈表以及雙鏈表的各種基本操作。

1：線性表抽象的數(shù)據(jù)類型

線性表：是由n（n>=0）個數(shù)據(jù)相同的元素組成的有限序列。線性表的定義接口如下

public interface IList<T> {
 /**
 * 是否為空
 * @return
 */
 boolean isEmpty();
 /**
 * 表的長度
 * @return
 */
 int length();
 /**
 * 根據(jù)索引獲取長度
 * @param i
 * @return
 */
 T get(int i);
 /**
 * 設置第i個元素值為x
 * @param i
 * @param x
 */
 void set(int i,T x);
 /**
 * 在線性表最后插入x元素
 * @param x
 */
 void append(T x);
 /**
 * 異常第i個元素并返回值
 * @param i
 * @return
 */
 T remove(int i);
 /**
 * 刪除線性表中所有元素
 */
 void removeAll();
 /**
 * 查詢首次出現(xiàn)關鍵字為key的元素
 * @param key
 * @return
 */
 T search(T key);
 void insert(int i,T x);
 /**
 * 升序添加
 * @param x
 */
 void insert(T x);
 /**
 * 升序刪除
 * @param x
 */
 void remove(T x);
}

2：線性表順序表示和實現(xiàn)

線性表的順序存儲結(jié)構是一組連續(xù)的內(nèi)存單元依次存放的線性表的數(shù)據(jù)元素，元素的物理地址和邏輯地址次序是相同的。我們叫做這種存儲方式為順序表。

由于數(shù)組只能進行賦值和取值，而且長度是不可變化的，所以給我們的操作帶來很大的麻煩，但是用順序表就可以進行刪除，插入等操作。其實順序表內(nèi)部同樣適用數(shù)組來表示的，只不過這個數(shù)據(jù)我們可以改變他的長度，這樣說來我們就好辦了，首先我們要為順序表定義一個數(shù)組，同時在定義一個值來記錄線性表的長度，所以第一步我們就有了如下

準備事件做好了以后，我們肯定會對順序表進行初始化，剛剛開始數(shù)組的長度肯定是0。但是我們必須要為數(shù)組開辟一個內(nèi)存空間，來存儲要插入的元素，如下

其他的都比較簡單，我主要說下插入和刪除

插入一個元素的時候，如果插在第i個位置，那么意味著它后面所有的元素前部往后面移一位，但是我們必須把i個位置留出來給即將插入的元素。但是我們還必須考慮，如果這個數(shù)組滿了的情況。如果滿了，我們必須重新為順序表開辟內(nèi)存空間，然后把以前的元素進行遷移到新的表中，java實現(xiàn)如下

代碼看出，我們把從第i個位置的元素全部往后移（包括第i個元素）然后在把第i個元素進行賦值

刪除第i個元素，這個和上面的正好相反，如果刪除第i個元素意味著在i之后的元素前部往前移一位。

3：順序表操作效率分析

因為順序表是具有索引的，所以get()和set()效率極高，時間復雜度都是O(n)。

從上面發(fā)現(xiàn)，在插入和刪除的時候都是需要大量元素的移動，因為在各個位置插入元素的概率相同，所以平均插入一個元素要移動的元素是2/n。那么它的時間復雜度就是O(n)，如果要容器滿了，那么就需要申請更大的容器來存儲新加入的元素，那么效率會更加的低下。所以順序表的靜態(tài)性好，動態(tài)性就很差了，所以在選擇的時候就要注意一下。

4：單鏈表的實現(xiàn)

線性表的鏈式存儲結(jié)構是用若干地址分散的存儲單元存儲數(shù)據(jù)元素，邏輯上相鄰的2個元素，物理地址不一定相同，這么說來就充分的利用了內(nèi)存中的地址。但是我們必須用附加信息來連接2個不同的數(shù)據(jù)元素，所以這里就引進了2個概念，數(shù)據(jù)域(data)和地址域(next)，其中數(shù)據(jù)域存儲的是這個元素的值，地址域存儲下一個元素的地址。其中數(shù)據(jù)域和地址域聯(lián)合起來我們稱為節(jié)點（node）。如果只有后繼節(jié)點沒有前驅(qū)節(jié)點我們就稱為單鏈表，那么現(xiàn)在我們來看看單鏈表的實現(xiàn)。

首先我們要定義一個節(jié)點Node

public class Node<T> {
 public T data;//數(shù)據(jù)域
 public Node next;//地址域
 public Node() {
 this(null, null);
 }
 public Node(T data, Node next) {
 this.data = data;
 this.next = next;
 }
}

現(xiàn)在我們想象一下，A(x)和B(y)2個節(jié)點，其中A的后繼節(jié)點是B，那么我們怎么表示呢，如下

Node<String> A=new Node<T>(x,null);
Node<String> B=new Node<T>(y,null);
A.next=B。

也可以把A寫成Node<String> A=new Node<T>(x,B);

ok現(xiàn)在我們正式開始實現(xiàn)一個帶有頭節(jié)點的單鏈表

我們可以把頭指針想象成一個指針來便于我們的操作，我們先看如何實現(xiàn)單鏈表的長度

public int length() {
 int i = 0;
 Node<T> p = this.head.next;
 while (p != null) {
  p = p.next;
  i++;
 }
 return i;
 }

因為這是一個鏈式的結(jié)構，我們無法得知長度，只能通過循環(huán)來知道鏈表中節(jié)點的個數(shù)，因為頭指針的后繼節(jié)點就是我們鏈表中第一個節(jié)點，所以我們就可以這樣往下循環(huán)來得知。

獲取第i個節(jié)點的值

同樣我們無法直接獲取節(jié)點，這個時候同樣采用循環(huán)，如果循環(huán)第i個元素值等于我們i那么我們就獲取這個節(jié)點，然后得到值

public T get(int i) {
 if (i >= 0) {
  Node<T> p = this.head;
  for (int j = 0; j <= i; j++) {
  p = p.next;
  }
  if (p!=null){
  return p.data;
  }
 }
 return null;
 }

在第i個位置插入一個節(jié)點

首先我們必須要找到要插入節(jié)點的前驅(qū)節(jié)點,然后前驅(qū)節(jié)點的后繼節(jié)點指向這個新節(jié)點，新節(jié)點的后繼節(jié)點指向原來前驅(qū)節(jié)點的后繼節(jié)點。