目錄
一、鏈表的簡單介紹
二、鏈表的接口
三、鏈表的方法實(shí)現(xiàn)
（1）display方法
（2）size得到單鏈表的長度方法
（3）addFirst頭插方法
（4）addLast尾插方法
（5）addIndex指定位置插入方法
（6）contains方法
（7）remove刪除第一個(gè)key值節(jié)點(diǎn)的方法
（8）removeAllKey刪除所有值為key的方法
（9）clear方法
四、最終代碼
一、鏈表的簡單介紹
概念：鏈表是一種物理存儲結(jié)構(gòu)不連續(xù)，邏輯上是連續(xù)的；鏈表類似現(xiàn)實(shí)中的火車，一節(jié)車廂連著一節(jié)車廂，而鏈表是通過鏈表之間的引用進(jìn)行連接，構(gòu)成一節(jié)一節(jié)的數(shù)據(jù)結(jié)構(gòu)。如圖：
二、鏈表的接口
代碼如下：
public interface Ilist {
//頭插法
void addFirst(int data);
//尾插法
void addLast(int data);
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
void addIndex(int index,int data);
//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
boolean contains(int key);
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
void remove(int key);
//刪除所有值為key的節(jié)點(diǎn)
void removeAllKey(int key);
//得到單鏈表的長度
int size();
void clear();
void display();
}
三、鏈表的方法實(shí)現(xiàn)
創(chuàng)建一個(gè)類，實(shí)現(xiàn)接口，重寫方法，鏈表中的方法都在里面實(shí)現(xiàn)。類里面有鏈表類，也是內(nèi)部類，有val值，next域，還有記錄第一個(gè)節(jié)點(diǎn)的頭結(jié)點(diǎn)，代碼如下：
public class MyLinkedList implements Ilist{
public ListNode head;
static class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
}我們先創(chuàng)建一個(gè)方法，方法里面會(huì)創(chuàng)建幾個(gè)節(jié)點(diǎn)，代碼如下：
public void createList() {
ListNode node1 = new ListNode(12);
ListNode node2 = new ListNode(23);
ListNode node3 = new ListNode(34);
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;
}調(diào)用這個(gè)方法，就會(huì)創(chuàng)建出含有5個(gè)節(jié)點(diǎn)的鏈表，在test類里面創(chuàng)建main方法，調(diào)用此方法后的結(jié)果，結(jié)果如圖：
（1）display方法
此方法可以顯示鏈表中所有元素，也就是遍歷一遍鏈表，打印val值，代碼如下：
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}調(diào)用該方法執(zhí)行結(jié)果如下：
（2）size得到單鏈表的長度方法
要得到鏈表的長度，就要遍歷一遍鏈表，定義一個(gè)變量進(jìn)行統(tǒng)計(jì)個(gè)數(shù)，代碼如下：
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}執(zhí)行結(jié)果：
（3）addFirst頭插方法
頭插就要把要插入的節(jié)點(diǎn)當(dāng)做頭結(jié)點(diǎn)，要插入的元素next域指向當(dāng)前頭結(jié)點(diǎn)，再把頭結(jié)點(diǎn)定成插入的元素。
代碼：
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
}調(diào)用此方法，多條語句后的執(zhí)行結(jié)果如下：
（4）addLast尾插方法
尾插就是要在鏈表的尾節(jié)點(diǎn)后插入節(jié)點(diǎn)，代碼如下：
public void addLast(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}執(zhí)行結(jié)果如下：
（5）addIndex指定位置插入方法
我們這里規(guī)定第一個(gè)節(jié)點(diǎn)的位置是0，第二個(gè)節(jié)點(diǎn)位置為1，依次往后推，我們要指定某一位置插入節(jié)點(diǎn)，先要檢查插入位置是否合法，不合法拋出異常；合法在指定位置插入節(jié)點(diǎn)，如果指定位置是0，就是頭插，指定位置是節(jié)點(diǎn)個(gè)數(shù)的size，就是尾插；中間位置，我們要找到指定位置的前一個(gè)節(jié)點(diǎn)，插入節(jié)點(diǎn)的next域指向前一個(gè)節(jié)點(diǎn)的next節(jié)點(diǎn)，前一個(gè)節(jié)點(diǎn)的next域指向插入節(jié)點(diǎn)，代碼如下：
public void addIndex(int index, int data) {
try {
if(index < 0 || index > size()) {
throw new IndexException("下標(biāo)異常,下標(biāo):" + index);
} else {
if(index == 0) {
//頭插
addFirst(data);
return;
}
if (index == size()) {
//尾插
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = searchPrev(index);
node.next = cur.next;
cur.next = node;
}
} catch (IndexException e) {
e.printStackTrace();
}
}
//找到鏈表前一個(gè)的位置
private ListNode searchPrev(int index) {
ListNode cur = this.head;
int count = 0;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}
public class IndexException extends RuntimeException{
public IndexException(String e) {
super(e);
}
}
（6）contains方法
查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中，遍歷一遍鏈表，有該元素就返回true，沒有就返回false，代碼如下：
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}（7）remove刪除第一個(gè)key值節(jié)點(diǎn)的方法
刪除一個(gè)節(jié)點(diǎn)，先要判斷該鏈表為不為空，為空就退出；不為空，看要?jiǎng)h的節(jié)點(diǎn)是不是頭結(jié)點(diǎn)，是頭結(jié)點(diǎn)就直接把頭結(jié)點(diǎn)改成頭結(jié)點(diǎn)的next域；要?jiǎng)h除的節(jié)點(diǎn)可能在中間，就要扎到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，把前一個(gè)節(jié)點(diǎn)的next域指向要?jiǎng)h除節(jié)點(diǎn)的next域就好了，代碼如下：
public void remove(int key) {
if(this.head == null) {
//一個(gè)節(jié)點(diǎn)都沒有，無法刪除
return;
}
if(this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = findPrev(key);
if(cur == null) {
System.out.println("沒有要?jiǎng)h除的點(diǎn)");
} else {
ListNode del = cur.next;
cur.next = del.next;
}
}
private ListNode findPrev(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if(cur.next.val == key) {
break;
}
cur = cur.next;
}
return cur == this.head ? null : cur;
}執(zhí)行結(jié)果如下：
（8）removeAllKey刪除所有值為key的方法
如果頭結(jié)點(diǎn)是空的，就不用進(jìn)行下面操作，直接返回。
兩個(gè)節(jié)點(diǎn)，一個(gè)的前節(jié)點(diǎn)，一個(gè)是前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，遍歷后一個(gè)節(jié)點(diǎn)，判斷后一個(gè)節(jié)點(diǎn)的val值是不是key，是key就把前一個(gè)節(jié)點(diǎn)的next域指向后一個(gè)節(jié)點(diǎn)的next域，后一個(gè)節(jié)點(diǎn)向后移，沒有命中后一個(gè)節(jié)點(diǎn)==key這條件，前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)都要往后移動(dòng)一步。
最后還要判斷頭結(jié)點(diǎn)的val值是否等于key值，是就要把head標(biāo)記成head的next域。
代碼入如下：
public void removeAllKey(int key) {
if(this.head == null) {
return;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next =cur.next;
cur = cur.next;
} else {
cur = cur.next;
prev = prev.next;
}
}
if(this.head.val == key) {
this.head = this.head.next;
}
}執(zhí)行結(jié)果如下：
（9）clear方法
清除所有節(jié)點(diǎn)，有兩種解決方案，第一種是直接把頭結(jié)點(diǎn)設(shè)為空，這種方法比較暴力；第二種是把每個(gè)節(jié)點(diǎn)的next域設(shè)為空，同時(shí)val也要設(shè)為空，因?yàn)檫@里的val類型是int，所以就設(shè)置不了空了，最后再把head節(jié)點(diǎn)設(shè)為空，代碼如下：
public void clear() {
ListNode cur = this.head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur = curNext;
}
head = null;
}執(zhí)行結(jié)果如下：文章來源：http://www.zghlxwxcb.cn/news/detail-773316.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-773316.html
四、最終代碼
public class MyLinkedList implements Ilist{
public ListNode head;
static class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public void createList() {
ListNode node1 = new ListNode(12);
ListNode node2 = new ListNode(23);
ListNode node3 = new ListNode(34);
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;
}
@Override
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
}
@Override
public void addLast(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
@Override
public void addIndex(int index, int data) {
try {
if(index < 0 || index > size()) {
throw new IndexException("下標(biāo)異常,下標(biāo):" + index);
} else {
if(index == 0) {
//頭插
addFirst(data);
return;
}
if (index == size()) {
//尾插
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = searchPrev(index);
node.next = cur.next;
cur.next = node;
}
} catch (IndexException e) {
e.printStackTrace();
}
}
//找到鏈表前一個(gè)的位置
private ListNode searchPrev(int index) {
ListNode cur = this.head;
int count = 0;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}
@Override
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
@Override
public void remove(int key) {
if(this.head == null) {
//一個(gè)節(jié)點(diǎn)都沒有，無法刪除
return;
}
if(this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = findPrev(key);
if(cur == null) {
System.out.println("沒有要?jiǎng)h除的點(diǎn)");
} else {
ListNode del = cur.next;
cur.next = del.next;
}
}
private ListNode findPrev(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if(cur.next.val == key) {
break;
}
cur = cur.next;
}
return cur == this.head ? null : cur;
}
@Override
public void removeAllKey(int key) {
if(this.head == null) {
return;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next =cur.next;
cur = cur.next;
} else {
cur = cur.next;
prev = prev.next;
}
}
if(this.head.val == key) {
this.head = this.head.next;
}
}
@Override
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
@Override
public void clear() {
ListNode cur = this.head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur = curNext;
}
head = null;
}
@Override
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
}
//自定義異常類
public class IndexException extends RuntimeException{
public IndexException(String e) {
super(e);
}
}
點(diǎn)個(gè)贊再走吧，謝謝謝謝謝！
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) 模擬實(shí)現(xiàn)LinkedList單向不循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
