目錄

一、鏈表的概念和結(jié)構(gòu)

1、概念

2、結(jié)構(gòu)

二、鏈表的分類

三、鏈表的實(shí)現(xiàn)

1、創(chuàng)建節(jié)點(diǎn)類?

2、定義表頭

3、創(chuàng)建鏈表

4、打印鏈表

5、鏈表長(zhǎng)度

6、看鏈表中是否包含key

?7、在index位置插入val（0下標(biāo)為第一個(gè)位置）

8、刪除第一個(gè)關(guān)鍵字key

9、刪除鏈表中所有key元素?

10、清空鏈表

?11、完整代碼

---

一、鏈表的概念和結(jié)構(gòu)

1、概念

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。

2、結(jié)構(gòu)

鏈表分為多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以由下圖表示：

其中，value為這個(gè)節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)的值，next為下一個(gè)節(jié)點(diǎn)的地址。以5個(gè)節(jié)點(diǎn)的鏈表為例，它們的數(shù)據(jù)值分別為12,23,34,45,56：

?

其中，第五個(gè)節(jié)點(diǎn)由于沒有后繼節(jié)點(diǎn)，所以next域存儲(chǔ)的是空指針null。

二、鏈表的分類

鏈表的結(jié)構(gòu)多種多樣，按以下情況分類：

1. 單向或者雙向

2. 帶頭或者不帶頭

3. 循環(huán)或者非循環(huán)

共可分出8種類型。

三、鏈表的實(shí)現(xiàn)

本篇文章我們主要用代碼實(shí)現(xiàn)無頭單向非循環(huán)鏈表。

1、創(chuàng)建節(jié)點(diǎn)類?

static class ListNode{//ListNode為一個(gè)節(jié)點(diǎn)public int val;public ListNode next;public ListNode(int val) {//構(gòu)造函數(shù)this.val = val;}
}

2、定義表頭

    //定義表頭public ListNode head;

3、創(chuàng)建鏈表

方法一：直接進(jìn)行val的賦值和對(duì)next的初始化?

    public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(26);ListNode node3=new ListNode(30);ListNode node4=new ListNode(45);ListNode node5=new ListNode(56);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}

?方法二：頭插法

    //頭插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}node.next=head;head=node;}

頭插法是指在頭節(jié)點(diǎn)的位置插入一個(gè)新節(jié)點(diǎn)。

    //尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}

尾插法是指在尾節(jié)點(diǎn)的位置插入一個(gè)新節(jié)點(diǎn)。

4、打印鏈表

    //打印鏈表public void show(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

注意：為了使head在打印的過程中不受影響，我們可以重新定義一個(gè)cur，把head賦值給cur，這樣head既不受影響，又可以繼續(xù)下面的操作，兩全其美。具體代碼為：ListNode cur=head;，以下同理。

5、鏈表長(zhǎng)度

    //鏈表長(zhǎng)度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}

6、看鏈表中是否包含key

    //看鏈表中是否包含keypublic boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}

?7、在index位置插入val（0下標(biāo)為第一個(gè)位置）

    //插入鏈表public void addIndex(int index,int val){if(index<0||index>size()){return;}if(index==0){addFirst(val);}else if(index==size()){addLast(val);}else{ListNode node=new ListNode(val);ListNode cur=findPindex(index);node.next=cur.next;cur.next=node;}}//找出index前一個(gè)節(jié)點(diǎn)private ListNode findPindex(int index){int i=1;ListNode cur=head;while(i<=index-1){cur=cur.next;i++;}return cur;}

?因?yàn)樵诓迦胫靶枵页鰅ndex的前一個(gè)節(jié)點(diǎn)，所以我們又創(chuàng)建了一個(gè)私有方法findPindex。

8、刪除第一個(gè)關(guān)鍵字key

    //刪除第一個(gè)出現(xiàn)的關(guān)鍵字keypublic void remove(int key){if(head==null){return;}if(head.val==key){head=head.next;}ListNode cur=findPkey(key);if(cur==null){return;}ListNode dve=cur.next;cur.next=dve.next;}//找出key前一個(gè)節(jié)點(diǎn)private ListNode findPkey(int key){ListNode cur=head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}

?因?yàn)樵趧h除之前需找出key的前一個(gè)節(jié)點(diǎn)，所以我們又創(chuàng)建了一個(gè)私有方法findPkey。

9、刪除鏈表中所有key元素?

    //刪除鏈表中的所有key元素public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}

10、清空鏈表

    public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.next=null;cur=curN;}head=null;}

?11、完整代碼

public class MySingleList {static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//定義表頭public ListNode head;//創(chuàng)建鏈表public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(26);ListNode node3=new ListNode(30);ListNode node4=new ListNode(45);ListNode node5=new ListNode(56);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}//打印鏈表public void show(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}//鏈表長(zhǎng)度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}//看鏈表中是否包含keypublic boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//頭插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}node.next=head;head=node;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}//插入鏈表public void addIndex(int index,int val){if(index<0||index>size()){return;}if(index==0){addFirst(val);}else if(index==size()){addLast(val);}else{ListNode node=new ListNode(val);ListNode cur=findPindex(index);node.next=cur.next;cur.next=node;}}//找出index前一個(gè)節(jié)點(diǎn)private ListNode findPindex(int index){int i=1;ListNode cur=head;while(i<=index-1){cur=cur.next;i++;}return cur;}//刪除第一個(gè)出現(xiàn)的關(guān)鍵字keypublic void remove(int key){if(head==null){return;}if(head.val==key){head=head.next;}ListNode cur=findPkey(key);if(cur==null){return;}ListNode dve=cur.next;cur.next=dve.next;}//找出key前一個(gè)節(jié)點(diǎn)private ListNode findPkey(int key){ListNode cur=head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}//刪除鏈表中的所有key元素public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.next=null;cur=curN;}head=null;}
}

以上便是本篇文章的全部?jī)?nèi)容，感謝大家的支持！下期見~~~