重試資料結構的單連結清單，一種說不出來的感覺，碼代碼就是一個坑，跳進去了，就爬不出來了，以前是用c++寫的連結清單，現在開始是用Java來寫一遍。按道理來說，原理都是一樣的，但是由于部落客自己以前太浪，以至于從前都不知道學了啥，是以這次算是重拾吧。
下面給大家分享一下本次寫單連結清單本寶寶給自己挖的坑或者自己掉進去的坑。
- 什麼是連結清單
- 連結清單的組成
- 連結清單的實作
我們可以嘗試使用現實生活中的例子去了解一下連結清單，鍊:一看到這個字，第一反應是不是狗鍊，連結等。當然這跟狗鍊的差別還是比較大的，但是不乏有共同的點。
1.連結清單是一種資料結構，而且跟數組隊列一樣都是線性表。但是他跟數組的差別就是，數組存儲的空間都是連續的，但是連結清單都是可以分散的，也就是分線性的（咱們要專業一點），因為引用域的存在（指針域的說法用于c++)，他存儲的是位址。是以隻要有位址，那麼每個節點的分布我都可以找到。就好比——你可以輕易找到中國的任意一個省份一樣。
那麼連結清單是用來幹啥呢，說了是一種資料結構，那麼就是存儲資料啦，有一些基本操作，比如，增删改查等。
優點：消除了數組需要預先配置設定記憶體大小的弊端。
缺點：引用域“占地面積”太大了，這是特别消耗記憶體的。
部落客還是想去偷張圖來給大家去看看連結清單長啥樣。
因為部落客畫畫是在太醜了，真的不想去嘗試，說多了都是淚。
2.從上面那個圖可以看到，組成由資料域加引用域
資料域就是存儲你想要存儲的資料啦，在這裡我們可以注意一下：
看這裡
當我們不知道自己要在連結清單裡面存儲什麼樣的資料類型的時候，那麼我們就可以使用泛型來标志。
泛型它不是一種資料類型，它隻是一個符号，可以泛指Java中的引用類型
3.開始寫連結清單
首先節點類：
節點類裡面包含資料域引用域，還要構造函數，如果我們的頭結點不存儲東西，那麼我們就需要構造一下沒有參數的函數。
public class Node<E>{
public E e;
public Node<E> next;
public Node() {
this.next=null;
this.e=null;
}
public Node(E e)
{
this.e=e;
this.next=null;
}
}
然後，我們就可以寫個連結清單類啦！在這裡主要給大家示範實作，增添元素，删除某位置的元素（根據位置插入某元素的原理差不多），還有反轉。
在這裡不得不提的一個小坑，哇，可我氣死啦，大概一個小時耗在在，沒錯，部落客就是這麼傻。
我剛開始呢，定義資料域和引用域的時候都是用的private，後來我發現在連結清單的構造函數裡，怎麼樣都不能讓資料域或者指針域為null;
這隻是因為，我把屬性定義為私有，哇，這麼基礎，然後，我傻傻的一直找啊，上網看啊看，真是慘痛的教訓。
（1）增添：
public void append(E e)
{
Node<E> node=new Node<E>(e);
if(size==0)
{
root.next=node;
tail=node;
}
else if(size>0)
{
tail.next=node;
tail=node;
}
size++;
}
這個其實沒事好說，但是就是要注意一個點，頭結點插入的時候一定要單獨寫出來，然後再定義尾節點。
（2）根據位置删除
既然是根據位置，那麼我們應該通過周遊來查找到此位置的元素咯，這其實就是跟數組比較得到的不好的地方了，數組的話，直接可以根據下标來找到我們需要的元素，但是連結清單的話，我們就需要根據頭結點來逐個周遊來找到。利用引用域，當然這也就可以看出來，每個節點之間聯系密切，就算分散開，我們也是可以找得到的。
那麼首先我們需要擷取到節點：
public Node<E> getNode(int index)
{
Node<E> node=new Node<E>();
node=root.next;
for(int i=0;i<=index-1;i++)//得到目前節點
{
node=node.next;
}
return node;
}
好啦，第二坑我的地方來了。我們定義的頭結點是不存儲東西的，那麼他到底算不算是我的第一個節點呢，答案是肯定的，他并不算，沒有存儲東西那就不算。是以我們需要主要，這個獲得的節點是目前的節點還是前一個節點，因為這都有一定的便利。
我這裡寫的就是獲得目前節點了，因為這裡會讓我有些繞，等你們親自體會就知道了，主要結合删除方法來看，你得時刻知道目前的節點，還有各種next。
然後接着就寫删除方法：
public E remove(int index)
{
Node<E> removeNode=getNode(index);
E data=removeNode.e;
Node<E> node;
if(index==size-1)
{
if(index==0)
{
root.next=null;
tail=root;
size--;
}
else
{
removeNode.next=null;
tail=removeNode;
size--;
}
}
else if(index==0)
{
root.next=removeNode.next;
removeNode.next=null;
size--;
}
else if(index<0||index>=size)
{
System.out.println("越界删除");
return null;
}
return data;
}
第三坑：我一開始的思路是，首先判斷是不是越界，（這個肯定有的），然後判斷是不是尾節點，接着判斷是不是删除0号元素，如果是，那麼就單獨寫，如果不是，那就是再寫。如果是尾節點，那麼判斷是不是删除0号元素，如果是，那就隻剩下頭結點了，不是再繼續寫。
但是這種方法使得的擷取節點的方式頻繁報錯，最後我就變成判斷，删除的位置是不是0
最後就是反轉：
突然用截圖，每次都好生氣的，編輯的時候自己就會突然發現bug,氣。就是粘貼不上來。
反轉的話，其實就是按照正常的思路，生成一個頭結點放在尾巴那裡，讓尾巴tail等于原來第0個節點。然後所有指針反向，注意一下，需要斷開反轉掉的指針。
最後的最後給大家一下測試樣例，驗證一下本寶寶的代碼：
Linked<String> link=new Linked<>();
link.append("abc");
link.append("def");
link.append("gh");
link.append("123");
link.append("12");
System.out.println("連結清單的長度為："+link.size());
for(int i=0;i<link.size();i++)
{
System.out.println("第"+i+"個元素為："+link.getvalue(i));
System.out.println();
}
link.remove(0);
System.out.println("連結清單的長度為："+link.size());
for(int i=0;i<link.size();i++)
{
System.out.println("第"+i+"個元素為："+link.getvalue(i));
System.out.println();
}
link.append("789");
link.append("10");
System.out.println("連結清單的長度為："+link.size());
for(int i=0;i<link.size();i++)
{
System.out.println("第"+i+"個元素為："+link.getvalue(i));
System.out.println();
}
link.remove(5);
System.out.println("連結清單的長度為："+link.size());
for(int i=0;i<link.size();i++)
{
System.out.println("第"+i+"個元素為："+link.getvalue(i));
System.out.println();
}
link.reverse();
for(int i=0;i<link.size();i++)
{
System.out.println("第"+i+"個元素為："+link.getvalue(i));
System.out.println();
}
首先是添加5個元素，然後連結清單長度為5；
周遊輸出五個自己添加的元素，看一下是否正确。
接着删除第0個元素，再周遊輸出，看一下是否成功删除。
然後再添加兩個元素，删除一個元素。輸出，反轉輸出。
從上面可以發現反轉成功。goodbye！