一、概述

單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表將采用一組任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。由于不需要按順序存儲(chǔ)，鏈表在插入、刪除數(shù)據(jù)元素時(shí)比順序存儲(chǔ)要快，但是在查找一個(gè)節(jié)點(diǎn)時(shí)則要比順序存儲(chǔ)要慢

使用鏈?zhǔn)酱鎯?chǔ)可以克服順序線性表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈?zhǔn)酱鎯?chǔ)失去了數(shù)組隨機(jī)存取的特點(diǎn)，同時(shí)增加了節(jié)點(diǎn)的指針域，空間開(kāi)銷(xiāo)較大。

二、圖解

下圖就是最簡(jiǎn)單最一般的單向鏈表：

新增節(jié)點(diǎn)：

將值為element的新節(jié)點(diǎn)插入到第index的位置上。

首先要先找到索引為index-1的節(jié)點(diǎn)，然后生成一個(gè)數(shù)據(jù)為element的新節(jié)點(diǎn)newNode，并令index-1處節(jié)點(diǎn)的next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的next指向原來(lái)index處的節(jié)點(diǎn)。

刪除節(jié)點(diǎn)：

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

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

下面的程序分別實(shí)現(xiàn)了線性表的初始化、獲取線性表長(zhǎng)度、獲取指定索引處元素、根據(jù)值查找、插入、刪除、清空等操作。

public class LinkList<T> { // 定義一個(gè)內(nèi)部類(lèi)Node，代表鏈表的節(jié)點(diǎn) private class Node { private T data;// 保存數(shù)據(jù) private Node next;// 指向下個(gè)節(jié)點(diǎn)的引用 // 無(wú)參構(gòu)造器 public Node() { } // 初始化全部屬性的構(gòu)造器 public Node(T data, Node next) { this.data = data; this.next = next; } } private Node header;// 保存頭結(jié)點(diǎn) private Node tail;// 保存尾節(jié)點(diǎn) private int size;// 保存已含有的節(jié)點(diǎn)數(shù) // 創(chuàng)建空鏈表 public LinkList() { header = null; tail = null; } // 已指定數(shù)據(jù)元素創(chuàng)建鏈表，只有一個(gè)元素 public LinkList(T element) { header = new Node(element, null); // 只有一個(gè)節(jié)點(diǎn)，header,tail都指向該節(jié)點(diǎn) tail = header; size++; } // 返回鏈表的長(zhǎng)度 public int length() { return size; } // 獲取指定索引處的元素 public T get(int index) { return this.getNodeByIndex(index).data; } //獲取指定位置的節(jié)點(diǎn) private Node getNodeByIndex(int index){ if(index < 0 || index > size-1){ throw new IndexOutOfBoundsException("索引超出線性表范圍"); } Node current = header;//從header開(kāi)始遍歷 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{ //當(dāng)index為0時(shí)，即在鏈表頭處插入 if(0 == index){ addAtHead(element); } else{ Node prev = getNodeByIndex(index - 1);//獲取前一個(gè)節(jié)點(diǎn) //讓prev的next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的next指向原來(lái)prev的下一個(gè)節(jié)點(diǎn) prev.next = new Node(element, prev.next); size++; } } } //在尾部插入元素 public void add(T element) { //如果鏈表是空的 if(header == null){ header = new Node(element, null); //只有一個(gè)節(jié)點(diǎn)，headwe,tail都該指向該節(jié)點(diǎn) tail = header; } else{ Node newNode = new Node(element, null);//創(chuàng)建新節(jié)點(diǎn) tail.next = newNode;//尾節(jié)點(diǎn)的next指向新節(jié)點(diǎn) tail = newNode;//將新節(jié)點(diǎn)作為尾節(jié)點(diǎn) } size++; } //頭部插入 public void addAtHead(T element){ //創(chuàng)建新節(jié)點(diǎn)，讓新節(jié)點(diǎn)的next指向header //并以新節(jié)點(diǎn)作為新的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; //若要?jiǎng)h除的是頭節(jié)點(diǎn) if(index == 0){ del = header; header = header.next; } else{ Node prev = getNodeByIndex(index - 1);//獲取待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) del = prev.next;//獲取待刪除節(jié)點(diǎn) prev.next = del.next; del.next = null;//將被刪除節(jié)點(diǎn)的next引用置為空 } size--; return del.data; } //刪除最后一個(gè)元素 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(); } } }

四、測(cè)試代碼

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

五、鏈表相關(guān)的常用操作實(shí)現(xiàn)方法

1. 鏈表反轉(zhuǎn)

/*** 鏈表反轉(zhuǎn)* * @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. 查找單鏈表的中間節(jié)點(diǎn)

采用快慢指針的方式查找單鏈表的中間節(jié)點(diǎn)，快指針一次走兩步，慢指針一次走一步，當(dāng)快指針走完時(shí)，慢指針剛好到達(dá)中間節(jié)點(diǎn)。

/*** 查找單鏈表的中間節(jié)點(diǎn)* * @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. 查找倒數(shù)第k個(gè)元素

采用兩個(gè)指針P1,P2，P1先前移K步，然后P1、P2同時(shí)移動(dòng)，當(dāng)p1移動(dòng)到尾部時(shí)，P2所指位置的元素即倒數(shù)第k個(gè)元素 。

/*** 查找倒數(shù) 第k個(gè)元素* * @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. 對(duì)鏈表進(jìn)行排序

/*** 排序* * @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. 刪除鏈表中的重復(fù)節(jié)點(diǎn)

/*** 刪除重復(fù)節(jié)點(diǎn)*/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. 從尾到頭輸出單鏈表，采用遞歸方式實(shí)現(xiàn)

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

7. 判斷鏈表是否有環(huán)，有環(huán)情況下找出環(huán)的入口節(jié)點(diǎn)

/*** 判斷鏈表是否有環(huán)，單向鏈表有環(huán)時(shí)，尾節(jié)點(diǎn)相同* * @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("該鏈表有環(huán)");return true;}}return !(fast == null || fast.next == null);}/*** 找出鏈表環(huán)的入口* * @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

總結(jié)

以上是生活随笔為你收集整理的单链表简易教程的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。