文章有不當之處，歡迎指正，如果喜歡微信閱讀，你也可以關注我的微信公眾號：好好學java，獲取優質學習資源。

一、概述

單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。

鏈式存儲結構的線性表將采用一組任意的存儲單元存放線性表中的數據元素。由于不需要按順序存儲，鏈表在插入、刪除數據元素時比順序存儲要快，但是在查找一個節點時則要比順序存儲要慢

使用鏈式存儲可以克服順序線性表需要預先知道數據大小的缺點，鏈表結構可以充分利用內存空間，實現靈活的內存動態管理。但是鏈式存儲失去了數組隨機存取的特點，同時增加了節點的指針域，空間開銷較大。

二、圖解

下圖就是最簡單最一般的單向鏈表：

這里寫圖片描述

新增節點：

將值為element的新節點插入到第index的位置上。

首先要先找到索引為index-1的節點，然后生成一個數據為element的新節點newNode，并令index-1處節點的next指向新節點，新節點的next指向原來index處的節點。

這里寫圖片描述

刪除節點：

刪除第index個節點，第index節點是由index-1出的節點引用的，因此刪除index的節點要先獲取index-1處的節點，然后讓index-1出節點的next引用到原index+1處的節點，并釋放index處節點即可。

這里寫圖片描述

三、單向鏈表的Java實現

下面的程序分別實現了線性表的初始化、獲取線性表長度、獲取指定索引處元素、根據值查找、插入、刪除、清空等操作。

public?class?LinkList<T>?{??//?定義一個內部類Node，代表鏈表的節點??private?class?Node?{??private?T?data;//?保存數據??private?Node?next;//?指向下個節點的引用??//?無參構造器??public?Node()?{??}??//?初始化全部屬性的構造器??public?Node(T?data,?Node?next)?{??this.data?=?data;??this.next?=?next;??}??}??private?Node?header;//?保存頭結點??private?Node?tail;//?保存尾節點??private?int?size;//?保存已含有的節點數??//?創建空鏈表??public?LinkList()?{??header?=?null;??tail?=?null;??}??//?已指定數據元素創建鏈表，只有一個元素??public?LinkList(T?element)?{??header?=?new?Node(element,?null);??//?只有一個節點，header,tail都指向該節點??tail?=?header;??size++;??}??//?返回鏈表的長度??public?int?length()?{??return?size;??}??//?獲取指定索引處的元素??public?T?get(int?index)?{??return?this.getNodeByIndex(index).data;??}??//獲取指定位置的節點??private?Node?getNodeByIndex(int?index){??if(index?<?0?||?index?>?size-1){??throw?new?IndexOutOfBoundsException("索引超出線性表范圍");??}??Node?current?=?header;//從header開始遍歷??for(int?i=0;?i<size?&&?current!=null;?i++,current=current.next){??if(i?==?index){??return?current;??}??}??return?null;??}??//按值查找所在位置??public?int?locate(T?element){??Node?current?=?header;??for(int?i=0;?i<size?&&?current!=null;?i++,?current=current.next){??if(current.data.equals(element)){??return?i;??}??}??return?-1;??}??//指定位置插入元素??public?void?insert(T?element,?int?index){??if(index?<?0?||?index?>?size){??throw?new?IndexOutOfBoundsException("索引超出線性表范圍");??}??//如果是空鏈表??if(header?==?null){??add(element);??}??else{??//當index為0時，即在鏈表頭處插入??if(0?==?index){??addAtHead(element);??}??else{??Node?prev?=?getNodeByIndex(index?-?1);//獲取前一個節點??//讓prev的next指向新節點，新節點的next指向原來prev的下一個節點??prev.next?=?new?Node(element,?prev.next);??size++;??}??}??}??//在尾部插入元素??public?void?add(T?element)?{??//如果鏈表是空的??if(header?==?null){??header?=?new?Node(element,?null);??//只有一個節點，headwe,tail都該指向該節點??tail?=?header;??}??else{??Node?newNode?=?new?Node(element,?null);//創建新節點??tail.next?=?newNode;//尾節點的next指向新節點??tail?=?newNode;//將新節點作為尾節點??}??size++;??}??//頭部插入??public?void?addAtHead(T?element){??//創建新節點，讓新節點的next指向header??//并以新節點作為新的header??Node?newNode?=?new?Node(element,?null);??newNode.next?=?header;??header?=?newNode;??//若插入前是空表??if(tail?==?null){??tail?=?header;??}??size++;??}??//刪除指定索引處的元素??public?T?delete(int?index){??if(index?<?0?||?index?>?size-1){??throw?new?IndexOutOfBoundsException("索引超出線性表范圍");??}??Node?del?=?null;??//若要刪除的是頭節點??if(index?==?0){??del?=?header;??header?=?header.next;??}??else{??Node?prev?=?getNodeByIndex(index?-?1);//獲取待刪除節點的前一個節點??del?=?prev.next;//獲取待刪除節點??prev.next?=?del.next;??del.next?=?null;//將被刪除節點的next引用置為空??}??size--;??return?del.data;??}??//刪除最后一個元素??public?T?remove(){??return?delete(size?-?1);??}??//判斷線性表是否為空??public?boolean?isEmpty(){??return?size?==?0;??}??//清空線性表??public?void?clear(){??//將header,tail置為null??header?=?null;??tail?=?null;??size?=?0;??}??public?String?toString(){??if(isEmpty()){??return?"[]";??}??else{??StringBuilder?sb?=?new?StringBuilder("[");??for(Node?current?=?header;?current?!=?null;?current?=?current.next){??sb.append(current.data.toString()?+?",?");??}??int?len?=?sb.length();??return?sb.delete(len-2,?len).append("]").toString();??}??}?? }??

四、測試代碼

import?org.junit.Test;?? import?com.sihai.algorithm.LinkList;?? public?class?LinkListTest?{??@Test??public?void?test()?{??//?測試構造函數??LinkList<String>?list?=?new?LinkList("好");??System.out.println(list);??//?測試添加元素??list.add("放大");??list.add("沒");??System.out.println(list);??//?在頭部添加??list.addAtHead("啦啦啦");??System.out.println(list);??//?在指定位置添加??list.insert("膜拜",?2);??System.out.println(list);??//?獲取指定位置處的元素??System.out.println("第2個元素是（從0開始計數）："?+?list.get(2));??//?返回元素索引??System.out.println("膜拜在的位置是："?+?list.locate("膜拜"));??System.out.println("mobai所在的位置："?+?list.locate("mobai"));??//?獲取長度??System.out.println("當前線性表的長度："?+?list.length());??//?判斷是否為空??System.out.println(list.isEmpty());??//?刪除最后一個元素??list.remove();??System.out.println("調用remove()后："?+?list);??//?獲取長度??System.out.println("當前線性表的長度："?+?list.length());??//?刪除指定位置處元素??list.delete(3);??System.out.println("刪除第4個元素后："?+?list);??//?獲取長度??System.out.println("當前線性表的長度："?+?list.length());??//?清空??list.clear();??System.out.println(list);??//?判斷是否為空??System.out.println(list.isEmpty());??}?? }??

五、鏈表相關的常用操作實現方法

1. 鏈表反轉

/***?鏈表反轉*?*?@param?head*?@return*/public?Node?ReverseIteratively(Node?head)?{Node?pReversedHead?=?head;Node?pNode?=?head;Node?pPrev?=?null;while?(pNode?!=?null)?{Node?pNext?=?pNode.next;if?(pNext?==?null)?{pReversedHead?=?pNode;}pNode.next?=?pPrev;pPrev?=?pNode;pNode?=?pNext;}this.head?=?pReversedHead;return?this.head;}

2. 查找單鏈表的中間節點

采用快慢指針的方式查找單鏈表的中間節點，快指針一次走兩步，慢指針一次走一步，當快指針走完時，慢指針剛好到達中間節點。

/***?查找單鏈表的中間節點*?*?@param?head*?@return*/public?Node?SearchMid(Node?head)?{Node?p?=?this.head,?q?=?this.head;while?(p?!=?null?&&?p.next?!=?null?&&?p.next.next?!=?null)?{p?=?p.next.next;q?=?q.next;}System.out.println("Mid:"?+?q.data);return?q;}

3. 查找倒數第k個元素

采用兩個指針P1,P2，P1先前移K步，然后P1、P2同時移動，當p1移動到尾部時，P2所指位置的元素即倒數第k個元素 。

/***?查找倒數?第k個元素*?*?@param?head*?@param?k*?@return*/public?Node?findElem(Node?head,?int?k)?{if?(k?<?1?||?k?>?this.length())?{return?null;}Node?p1?=?head;Node?p2?=?head;for?(int?i?=?0;?i?<?k;?i++)//?前移k步p1?=?p1.next;while?(p1?!=?null)?{p1?=?p1.next;p2?=?p2.next;}return?p2;}

4. 對鏈表進行排序

/***?排序*?*?@return*/public?Node?orderList()?{Node?nextNode?=?null;int?tmp?=?0;Node?curNode?=?head;while?(curNode.next?!=?null)?{nextNode?=?curNode.next;while?(nextNode?!=?null)?{if?(curNode.data?>?nextNode.data)?{tmp?=?curNode.data;curNode.data?=?nextNode.data;nextNode.data?=?tmp;}nextNode?=?nextNode.next;}curNode?=?curNode.next;}return?head;}

5. 刪除鏈表中的重復節點

/***?刪除重復節點*/public?void?deleteDuplecate(Node?head)?{Node?p?=?head;while?(p?!=?null)?{Node?q?=?p;while?(q.next?!=?null)?{if?(p.data?==?q.next.data)?{q.next?=?q.next.next;}?elseq?=?q.next;}p?=?p.next;}}

6. 從尾到頭輸出單鏈表，采用遞歸方式實現

/***?從尾到頭輸出單鏈表，采用遞歸方式實現*?*?@param?pListHead*/public?void?printListReversely(Node?pListHead)?{if?(pListHead?!=?null)?{printListReversely(pListHead.next);System.out.println("printListReversely:"?+?pListHead.data);}}

7. 判斷鏈表是否有環，有環情況下找出環的入口節點

/***?判斷鏈表是否有環，單向鏈表有環時，尾節點相同*?*?@param?head*?@return*/public?boolean?IsLoop(Node?head)?{Node?fast?=?head,?slow?=?head;if?(fast?==?null)?{return?false;}while?(fast?!=?null?&&?fast.next?!=?null)?{fast?=?fast.next.next;slow?=?slow.next;if?(fast?==?slow)?{System.out.println("該鏈表有環");return?true;}}return?!(fast?==?null?||?fast.next?==?null);}/***?找出鏈表環的入口*?*?@param?head*?@return*/public?Node?FindLoopPort(Node?head)?{Node?fast?=?head,?slow?=?head;while?(fast?!=?null?&&?fast.next?!=?null)?{slow?=?slow.next;fast?=?fast.next.next;if?(slow?==?fast)break;}if?(fast?==?null?||?fast.next?==?null)return?null;slow?=?head;while?(slow?!=?fast)?{slow?=?slow.next;fast?=?fast.next;}return?slow;}

參考資料：

• https://www.cnblogs.com/ganchuanpu/p/7468555.html
• https://blog.csdn.net/jianyuerensheng/article/details/51200274

總結

以上是生活随笔為你收集整理的自己动手写一个单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。