帶你瞭解Java數據結構和算法之鏈表
前面博客我們在講解數組中，知道數組作為數據存儲結構有一定的缺陷。在無序數組中，搜索性能差，在有序數組中，插入效率又很低，而且這兩種數組的刪除效率都很低，並且數組在創建後，其大小是固定瞭，設置的過大會造成內存的浪費，過小又不能滿足數據量的存儲。
本篇博客我們將講解一種新型的數據結構——鏈表。我們知道數組是一種通用的數據結構，能用來實現棧、隊列等很多數據結構。而鏈表也是一種使用廣泛的通用數據結構，它也可以用來作為實現棧、隊列等數據結構的基礎，基本上除非需要頻繁的通過下標來隨機訪問各個數據，否則很多使用數組的地方都可以用鏈表來代替。
但是我們需要說明的是，鏈表是不能解決數據存儲的所有問題的，它也有它的優點和缺點。本篇博客我們介紹幾種常見的鏈表，分別是單向鏈表、雙端鏈表、有序鏈表、雙向鏈表以及有迭代器的鏈表。並且會講解一下抽象數據類型（ADT）的思想，如何用 ADT 描述棧和隊列，如何用鏈表代替數組來實現棧和隊列。
1、鏈表（Linked List）
鏈表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的鏈接（"links"）
鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。
使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去瞭數組隨機讀取的優點，同時鏈表由於增加瞭結點的指針域，空間開銷比較大。
2、單向鏈表（Single-Linked List）
單鏈表是鏈表中結構最簡單的。一個單鏈表的節點(Node)分為兩個部分，第一個部分(data)保存或者顯示關於節點的信息，另一個部分存儲下一個節點的地址。最後一個節點存儲地址的部分指向空值。
單向鏈表隻可向一個方向遍歷，一般查找一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。而插入一個節點，對於單向鏈表，我們隻提供在鏈表頭插入，隻需要將當前插入的節點設置為頭節點，next指向原頭節點即可。刪除一個節點，我們將該節點的上一個節點的next指向該節點的下一個節點。
在表頭增加節點：
刪除節點：
①、單向鏈表的具體實現
package com.ys.datastructure;
public class SingleLinkedList {
private int size;//鏈表節點的個數
private Node head;//頭節點
public SingleLinkedList(){
size = 0;
head = null;
}
//鏈表的每個節點類
private class Node{
private Object data;//每個節點的數據
private Node next;//每個節點指向下一個節點的連接
public Node(Object data){
this.data = data;
}
}
//在鏈表頭添加元素
public Object addHead(Object obj){
Node newHead = new Node(obj);
if(size == 0){
head = newHead;
}else{
newHead.next = head;
head = newHead;
}
size++;
return obj;
}
//在鏈表頭刪除元素
public Object deleteHead(){
Object obj = head.data;
head = head.next;
size--;
return obj;
}
//查找指定元素，找到瞭返回節點Node，找不到返回null
public Node find(Object obj){
Node current = head;
int tempSize = size;
while(tempSize > 0){
if(obj.equals(current.data)){
return current;
}else{
current = current.next;
}
tempSize--;
}
return null;
}
//刪除指定的元素，刪除成功返回true
public boolean delete(Object value){
if(size == 0){
return false;
}
Node current = head;
Node previous = head;
while(current.data != value){
if(current.next == null){
return false;
}else{
previous = current;
current = current.next;
}
}
//如果刪除的節點是第一個節點
if(current == head){
head = current.next;
size--;
}else{//刪除的節點不是第一個節點
previous.next = current.next;
size--;
}
return true;
}
//判斷鏈表是否為空
public boolean isEmpty(){
return (size == 0);
}
//顯示節點信息
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){//當前鏈表隻有一個節點
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else{
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else{//如果鏈表一個節點都沒有，直接打印[]
System.out.println("[]");
}
}
}
測試：
@Test
public void testSingleLinkedList(){
SingleLinkedList singleList = new SingleLinkedList();
singleList.addHead("A");
singleList.addHead("B");
singleList.addHead("C");
singleList.addHead("D");
//打印當前鏈表信息
singleList.display();
//刪除C
singleList.delete("C");
singleList.display();
//查找B
System.out.println(singleList.find("B"));
}
打印結果：
②、用單向鏈表實現棧
棧的pop()方法和push()方法，對應於鏈表的在頭部刪除元素deleteHead()以及在頭部增加元素addHead()。
package com.ys.datastructure;
public class StackSingleLink {
private SingleLinkedList link;
public StackSingleLink(){
link = new SingleLinkedList();
}
//添加元素
public void push(Object obj){
link.addHead(obj);
}
//移除棧頂元素
public Object pop(){
Object obj = link.deleteHead();
return obj;
}
//判斷是否為空
public boolean isEmpty(){
return link.isEmpty();
}
//打印棧內元素信息
public void display(){
link.display();
}
}
4、雙端鏈表
對於單項鏈表，我們如果想在尾部添加一個節點，那麼必須從頭部一直遍歷到尾部，找到尾節點，然後在尾節點後面插入一個節點。這樣操作很麻煩，如果我們在設計鏈表的時候多個對尾節點的引用，那麼會簡單很多。
註意和後面將的雙向鏈表的區別！！！
①、雙端鏈表的具體實現
package com.ys.link;
public class DoublePointLinkedList {
private Node head;//頭節點
private Node tail;//尾節點
private int size;//節點的個數
private class Node{
private Object data;
private Node next;
public Node(Object data){
this.data = data;
}
}
public DoublePointLinkedList(){
size = 0;
head = null;
tail = null;
}
//鏈表頭新增節點
public void addHead(Object data){
Node node = new Node(data);
if(size == 0){//如果鏈表為空，那麼頭節點和尾節點都是該新增節點
head = node;
tail = node;
size++;
}else{
node.next = head;
head = node;
size++;
}
}
//鏈表尾新增節點
public void addTail(Object data){
Node node = new Node(data);
if(size == 0){//如果鏈表為空，那麼頭節點和尾節點都是該新增節點
head = node;
tail = node;
size++;
}else{
tail.next = node;
tail = node;
size++;
}
}
//刪除頭部節點，成功返回true，失敗返回false
public boolean deleteHead(){
if(size == 0){//當前鏈表節點數為0
return false;
}
if(head.next == null){//當前鏈表節點數為1
head = null;
tail = null;
}else{
head = head.next;
}
size--;
return true;
}
//判斷是否為空
public boolean isEmpty(){
return (size ==0);
}
//獲得鏈表的節點個數
public int getSize(){
return size;
}
//顯示節點信息
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){//當前鏈表隻有一個節點
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else{
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else{//如果鏈表一個節點都沒有，直接打印[]
System.out.println("[]");
}
}
}
②、用雙端鏈表實現隊列
package com.ys.link;
public class QueueLinkedList {
private DoublePointLinkedList dp;
public QueueLinkedList(){
dp = new DoublePointLinkedList();
}
public void insert(Object data){
dp.addTail(data);
}
public void delete(){
dp.deleteHead();
}
public boolean isEmpty(){
return dp.isEmpty();
}
public int getSize(){
return dp.getSize();
}
public void display(){
dp.display();
}
}
5、抽象數據類型（ADT）
在介紹抽象數據類型的時候，我們先看看什麼是數據類型，聽到這個詞，在Java中我們可能首先會想到像 int,double這樣的詞，這是Java中的基本數據類型，一個數據類型會涉及到兩件事：
- ①、擁有特定特征的數據項
- ②、在數據上允許的操作
比如Java中的int數據類型，它表示整數，取值范圍為：-2147483648~2147483647，還能使用各種操作符，+、-、*、/ 等對其操作。數據類型允許的操作是它本身不可分離的部分，理解類型包括理解什麼樣的操作可以應用在該類型上。
那麼當年設計計算機語言的人，為什麼會考慮到數據類型？
我們先看這樣一個例子，比如，大傢都需要住房子，也都希望房子越大越好。但顯然，沒有錢，考慮房子沒有意義。於是就出現瞭各種各樣的商品房，有別墅的、復式的、錯層的、單間的……甚至隻有兩平米的膠囊房間。這樣做的意義是滿足不同人的需要。
同樣，在計算機中，也存在相同的問題。計算1+1這樣的表達式不需要開辟很大的存儲空間，不需要適合小數甚至字符運算的內存空間。於是計算機的研究者們就考慮，要對數據進行分類，分出來多種數據類型。比如int，比如float。
雖然不同的計算機有不同的硬件系統，但實際上高級語言編寫者才不管程序運行在什麼計算機上，他們的目的就是為瞭實現整形數字的運算，比如a+b等。他們才不關心整數在計算機內部是如何表示的，也不管CPU是如何計算的。於是我們就考慮，無論什麼計算機、什麼語言都會面臨類似的整數運算，我們可以考慮將其抽象出來。抽象是抽取出事物具有的普遍性本質，是對事物的一個概括，是一種思考問題的方式。
抽象數據類型（ADT）是指一個數學模型及定義在該模型上的一組操作。它僅取決於其邏輯特征，而與計算機內部如何表示和實現無關。比如剛才說得整型，各個計算機，不管大型機、小型機、PC、平板電腦甚至智能手機，都有“整型”類型，也需要整形運算，那麼整型其實就是一個抽象數據類型。
更廣泛一點的，比如我們剛講解的棧和隊列這兩種數據結構，我們分別使用瞭數組和鏈表來實現，比如棧，對於使用者隻需要知道pop()和push()方法或其它方法的存在以及如何使用即可，使用者不需要知道我們是使用的數組或是鏈表來實現的。
ADT的思想可以作為我們設計工具的理念，比如我們需要存儲數據，那麼就從考慮需要在數據上實現的操作開始，需要存取最後一個數據項嗎？還是第一個？還是特定值的項？還是特定位置的項？回答這些問題會引出ADT的定義，隻有完整的定義瞭ADT後，才應該考慮實現的細節。
這在我們Java語言中的接口設計理念是想通的。
6、有序鏈表
前面的鏈表實現插入數據都是無序的，在有些應用中需要鏈表中的數據有序，這稱為有序鏈表。
在有序鏈表中，數據是按照關鍵值有序排列的。一般在大多數需要使用有序數組的場合也可以使用有序鏈表。有序鏈表優於有序數組的地方是插入的速度（因為元素不需要移動），另外鏈表可以擴展到全部有效的使用內存，而數組隻能局限於一個固定的大小中。
package com.ys.datastructure;
public class OrderLinkedList {
private Node head;
private class Node{
private int data;
private Node next;
public Node(int data){
this.data = data;
}
}
public OrderLinkedList(){
head = null;
}
//插入節點，並按照從小打到的順序排列
public void insert(int value){
Node node = new Node(value);
Node pre = null;
Node current = head;
while(current != null && value > current.data){
pre = current;
current = current.next;
}
if(pre == null){
head = node;
head.next = current;
}else{
pre.next = node;
node.next = current;
}
}
//刪除頭節點
public void deleteHead(){
head = head.next;
}
public void display(){
Node current = head;
while(current != null){
System.out.print(current.data+" ");
current = current.next;
}
System.out.println("");
}
}
在有序鏈表中插入和刪除某一項最多需要O(N)次比較，平均需要O(N/2)次，因為必須沿著鏈表上一步一步走才能找到正確的插入位置，然而可以最快速度刪除最值，因為隻需要刪除表頭即可，如果一個應用需要頻繁的存取最小值，且不需要快速的插入，那麼有序鏈表是一個比較好的選擇方案。比如優先級隊列可以使用有序鏈表來實現。
7、有序鏈表和無序數組組合排序
比如有一個無序數組需要排序，前面我們在講解冒泡排序、選擇排序、插入排序這三種簡單的排序時，需要的時間級別都是O(N2)。
現在我們講解瞭有序鏈表之後，對於一個無序數組，我們先將數組元素取出，一個一個的插入到有序鏈表中，然後將他們從有序鏈表中一個一個刪除，重新放入數組，那麼數組就會排好序瞭。和插入排序一樣，如果插入瞭N個新數據，那麼進行大概N2/4次比較。但是相對於插入排序，每個元素隻進行瞭兩次排序，一次從數組到鏈表，一次從鏈表到數組，大概需要2*N次移動，而插入排序則需要N2次移動，
效率肯定是比前面講的簡單排序要高，但是缺點就是需要開辟差不多兩倍的空間，而且數組和鏈表必須在內存中同時存在，如果有現成的鏈表可以用，那麼這種方法還是挺好的。
8、雙向鏈表
我們知道單向鏈表隻能從一個方向遍歷，那麼雙向鏈表它可以從兩個方向遍歷。
具體代碼實現：
package com.ys.datastructure;
public class TwoWayLinkedList {
private Node head;//表示鏈表頭
private Node tail;//表示鏈表尾
private int size;//表示鏈表的節點個數
private class Node{
private Object data;
private Node next;
private Node prev;
public Node(Object data){
this.data = data;
}
}
public TwoWayLinkedList(){
size = 0;
head = null;
tail = null;
}
//在鏈表頭增加節點
public void addHead(Object value){
Node newNode = new Node(value);
if(size == 0){
head = newNode;
tail = newNode;
size++;
}else{
head.prev = newNode;
newNode.next = head;
head = newNode;
size++;
}
}
//在鏈表尾增加節點
public void addTail(Object value){
Node newNode = new Node(value);
if(size == 0){
head = newNode;
tail = newNode;
size++;
}else{
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
size++;
}
}
//刪除鏈表頭
public Node deleteHead(){
Node temp = head;
if(size != 0){
head = head.next;
head.prev = null;
size--;
}
return temp;
}
//刪除鏈表尾
public Node deleteTail(){
Node temp = tail;
if(size != 0){
tail = tail.prev;
tail.next = null;
size--;
}
return temp;
}
//獲得鏈表的節點個數
public int getSize(){
return size;
}
//判斷鏈表是否為空
public boolean isEmpty(){
return (size == 0);
}
//顯示節點信息
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){//當前鏈表隻有一個節點
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else{
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else{//如果鏈表一個節點都沒有，直接打印[]
System.out.println("[]");
}
}
}
我們也可以用雙向鏈表來實現雙端隊列，這裡就不做具體代碼演示瞭。
9、總結
上面我們講瞭各種鏈表，每個鏈表都包括一個LinikedList對象和許多Node對象，LinkedList對象通常包含頭和尾節點的引用，分別指向鏈表的第一個節點和最後一個節點。而每個節點對象通常包含數據部分data，以及對上一個節點的引用prev和下一個節點的引用next，隻有下一個節點的引用稱為單向鏈表，兩個都有的稱為雙向鏈表。next值為null則說明是鏈表的結尾，如果想找到某個節點，我們必須從第一個節點開始遍歷，不斷通過next找到下一個節點，直到找到所需要的。棧和隊列都是ADT，可以用數組來實現，也可以用鏈表實現。
本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!