簡(jiǎn)介
鏈表是一種物理存儲(chǔ)單元上非連續(xù)依疼、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的而芥。
數(shù)組和鏈表
上一篇文章寫了數(shù)組的一些特性律罢，我們這里就拿數(shù)組跟鏈表做為比較來學(xué)習(xí)一些鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)吧。
數(shù)組和鏈表在內(nèi)存上的區(qū)別就跟示意圖一樣棍丐，上一篇文章寫了件蚕，數(shù)組的一個(gè)特點(diǎn)就是內(nèi)存的連續(xù)性旅薄，而鏈表不是，鏈表不要求所有數(shù)據(jù)都連續(xù)存儲(chǔ)，而是用一個(gè)“指針”將他們串在一起辨宠。
單鏈表
單鏈表是最簡(jiǎn)單的一種鏈表，從圖中可以看出答姥，鏈表第一個(gè)節(jié)點(diǎn)（頭結(jié)點(diǎn)）記錄著鏈表的起始地址莫鸭，用它能遍歷整個(gè)鏈表潦匈，尾節(jié)點(diǎn)指針指向一個(gè)空地址null，說明鏈表結(jié)束了赚导。
和數(shù)組一樣茬缩，鏈表也有查找刪除插入等操作。上一篇中寫了數(shù)組的刪除插入操作是很高復(fù)雜度的操作吼旧，每次刪除插入都有搬移數(shù)據(jù)凰锡，復(fù)雜度為O(n)，而鏈表卻不用圈暗，因?yàn)殒湵硎怯谩爸羔槨眮泶鎯?chǔ)下一節(jié)點(diǎn)的地址的掂为，所以無需數(shù)據(jù)搬移，插入操作只要將前一節(jié)點(diǎn)指針指向待插入數(shù)據(jù)员串，將待插入數(shù)據(jù)的指針指向原有節(jié)點(diǎn)的下一節(jié)點(diǎn)勇哗，就完成了插入操作，刪除也一樣昵济，復(fù)雜度為O(1)智绸。
然而鏈表也并非是完美的，相對(duì)于數(shù)組访忿，因?yàn)閿?shù)組內(nèi)存的連續(xù)性瞧栗，隨意數(shù)組的隨機(jī)訪問就可以做到O（1）的復(fù)雜度，而鏈表無法根據(jù)內(nèi)存地址的偏移來計(jì)算出某個(gè)節(jié)點(diǎn)的地址海铆，所需想要隨機(jī)訪問一個(gè)鏈表中的數(shù)據(jù)迹恐，需要遍歷整個(gè)鏈表來找到要訪問的節(jié)點(diǎn)，其算法復(fù)雜度是為O（n）卧斟。
#單鏈表的java實(shí)現(xiàn) SingleList.java
public class SingleList {
private Node head=null;
public SingleList(){
head=new Node(null);
head.next=null;
}
public int length(){
int length=0;
Node temp=head;
while (temp.next!=null){
length++;
temp=temp.next;
}
return length;
}
public void addNode(Node node){
Node temp=head;
while (temp.next!=null){
temp=temp.next;
}
temp.next=node;
}
public void addNode(Node node,int index) throws Exception {
if (index<0||index>length()+1){
throw new Exception("不合法index殴边！");
}
int currentIndex=0;
Node temp=head;
while (temp.next != null) {
if (index== currentIndex++){
node.next=temp.next;
temp.next=node;
return;
}
temp=temp.next;
}
}
public void delNode(Node node){
Node temp=head;
while (temp.next != null) {
if (temp.data==node.data){
node.next=temp.next;
temp.next=node;
return;
}
temp=temp.next;
}
}
public void delNode(int index) throws Exception {
if (index<1||index>length()+1){
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next != null) {
if (index==currentIndex++){
temp.next=temp.next.next;
return;
}
temp=temp.next;
}
}
public Node getNode(int index) throws Exception {
if (index < 1 || index > length() + 1) {
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next!=null){
if (index == currentIndex++) {
return temp;
}
temp=temp.next;
}
return null;
}
public void show(){
Node temp=head;
while (temp.next != null) {
temp=temp.next;
System.out.println(temp.data+";");
}
}
}
class Node{
public Object data;
public Node next;
public Node(Object data){
this.data=data;
}
}
#測(cè)試 main.java
public static void main(String[] args) {
SingleList singleList=new SingleList();
singleList.addNode(new Node(1));
singleList.addNode(new Node(2));
System.out.println("singleList Length="+singleList.length());
singleList.show();
try {
singleList.addNode(new Node(0),0);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("after addNode by index singleList Length="+singleList.length());
singleList.show();
try {
singleList.delNode(2);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("after delNode by index singleList Length="+singleList.length());
singleList.show();
singleList.delNode(new Node(1));
try {
System.out.println("node 2="+singleList.getNode(2));
} catch (Exception e) {
e.printStackTrace();
}
}
循環(huán)鏈表
循環(huán)鏈表也比較簡(jiǎn)單，就是在單鏈表的尾節(jié)點(diǎn)將原本指向null 的指針變?yōu)橹赶蝾^結(jié)點(diǎn)珍语。然后實(shí)現(xiàn)代碼也是跟單鏈表差不多锤岸，只是有幾個(gè)地方需要注意一下。
#CircularList.java
public class CircularList {
private Node head=null;
public CircularList(){
head=new Node(-1);
head.next=head;
}
public int length(){
int length=0;
Node temp=head;
while (temp.next!=head){
length++;
temp=temp.next;
}
return length;
}
public void addNode(Node node){
if (head.next==head){
head.next=node;
node.next=head;
}else {
Node temp=head;
while (temp.next!=head){
temp=temp.next;
}
temp.next=node;
node.next=head;
}
}
public void addNode(Node node,int index) throws Exception {
if (index<0||index>length()+1){
throw new Exception("不合法index板乙！");
}
int currentIndex=0;
Node temp=head;
while (temp.next != head) {
if (index== currentIndex++){
node.next=temp.next;
temp.next=node;
return;
}
temp=temp.next;
}
}
public void delNode(Node node){
Node temp=head;
while (temp.next.data != head.data) {
if (temp.next.data==node.data){
temp.next=temp.next.next;
System.out.println("del:"+node.data);
return;
}
temp=temp.next;
}
}
public void delNode(int index) throws Exception {
if (index<1||index>length()+1){
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next != head) {
if (index==currentIndex++){
temp.next=temp.next.next;
return;
}
temp=temp.next;
}
}
public Node getNode(int index) throws Exception {
if (index < 1 || index > length() + 1) {
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next!=head){
if (index == currentIndex++) {
return temp;
}
temp=temp.next;
}
return null;
}
public void show(){
Node temp=head;
while (temp.next != head) {
temp=temp.next;
System.out.println(temp.data+"->"+temp.next.data);
}
}
}
循環(huán)鏈表實(shí)現(xiàn)完了是偷，我們接下來用它來實(shí)現(xiàn)一個(gè)循環(huán)鏈表的經(jīng)典問題“約瑟夫環(huán)”，這個(gè)問題的數(shù)學(xué)描述是這樣的：已知n個(gè)人（以編號(hào)1募逞，2蛋铆，3...n分別表示）圍坐在一張圓桌周圍。從編號(hào)為k的人開始報(bào)數(shù)放接，數(shù)到m的那個(gè)人出列刺啦；他的下一個(gè)人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列纠脾；依此規(guī)律重復(fù)下去玛瘸，直到圓桌周圍的人全部出列蜕青。
# jusephus.java
public static void main(String[] args) {
jusephus(30,5,3);
}
private static void jusephus(int n,int k,int m){
CircularList circularList=new CircularList();
for (int i = 0; i < n; i++) {
circularList.addNode(new Node(i));
}
int count=m;
Node startNode=null;
try {
startNode=circularList.getNode(k);
} catch (Exception e) {
e.printStackTrace();
}
while (circularList.length()>0){
if (--count>0){
startNode=startNode.next;
}
if (count==0){
System.out.println("out:"+startNode.data+" m="+m+" c l="+circularList.length());
circularList.delNode(startNode);
startNode=startNode.next;
count=m;
}
}
}
雙向鏈表
雙向鏈表顧名思義不僅有一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針，還有一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針捧韵。
從圖中可以看出市咆，雙向鏈表會(huì)比單鏈表多一個(gè)字節(jié)的內(nèi)存空間來存儲(chǔ)前驅(qū)節(jié)點(diǎn)，所謂有得必有失再来，那么雙向鏈表比單鏈表多了什么特性呢？
由于多了一個(gè)前向指針磷瘤，雙向鏈表支持O（1）時(shí)間復(fù)雜度查找前驅(qū)節(jié)點(diǎn)芒篷，在某些情況下雙向鏈表的插入刪除操作比單鏈表高效；對(duì)于單鏈表采缚，前面已經(jīng)寫了针炉，他的插入、刪除操作的時(shí)間復(fù)雜度都是O(1)扳抽，那么還有比這更高效的篡帕？這就要先看下實(shí)際情況下刪除操作所包含的情況了：
很多情況下我們刪除一個(gè)節(jié)點(diǎn)都是只知道某個(gè)值，然后要?jiǎng)h除這個(gè)值所在節(jié)點(diǎn)贸呢，那么這個(gè)時(shí)候想要找到這個(gè)節(jié)點(diǎn)镰烧，就需要遍歷整個(gè)鏈表，從頭遍歷一次找到節(jié)點(diǎn)然后再執(zhí)行刪除操作楞陷，這時(shí)候復(fù)雜度就退化到了O（n）怔鳖，這種情況下無論是單鏈表還是雙向鏈表都沒有差別；還有一種情況是我們已經(jīng)知道要?jiǎng)h除的是一個(gè)節(jié)點(diǎn)固蛾，刪除這個(gè)節(jié)點(diǎn)之前我們需要得到所要?jiǎng)h除的節(jié)點(diǎn)的前向節(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)结执，對(duì)于單鏈表，我們想要知道前向節(jié)點(diǎn)就不得不重新變量所有的節(jié)點(diǎn)以找到它艾凯，這個(gè)時(shí)候献幔，雙向鏈表的優(yōu)勢(shì)就體現(xiàn)出來了，因?yàn)樗粌H存儲(chǔ)了后續(xù)節(jié)點(diǎn)的指針趾诗，還存儲(chǔ)了前向節(jié)點(diǎn)的指針蜡感，所以這種情況下，雙向鏈表的刪除操作無需遍歷找到前向節(jié)點(diǎn)沧竟，此時(shí)铸敏，刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度就僅為O(1)。同理悟泵，插入操作時(shí)雙向鏈表也比單鏈表會(huì)高效杈笔。
總結(jié)
鏈表雖然相較于數(shù)組會(huì)更方便，但是因?yàn)槊總€(gè)節(jié)點(diǎn)要多存儲(chǔ)一個(gè)或者兩個(gè)指針數(shù)據(jù)糕非，所以在內(nèi)存耗費(fèi)上會(huì)比數(shù)組消耗更大蒙具，所以具體使用數(shù)組還是鏈表還得根據(jù)實(shí)際情況來決定球榆。
