鏈表

1、基本介紹

• 什么是鏈表？

  鏈表（Linked List）是用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的線性表。鏈表示意圖：

  

• 鏈表的組成：數(shù)據(jù)域+引用域（數(shù)據(jù)域和引用域合稱結(jié)點(diǎn)或元素）

  • 數(shù)據(jù)域存放數(shù)據(jù)元素自身的數(shù)據(jù)
  • 引用域存放相鄰結(jié)點(diǎn)的地址

• 鏈表的特點(diǎn)：

  • 鏈表中元素的聯(lián)系依靠引用域

  • 具有線性結(jié)構(gòu)的特點(diǎn)，鏈表所使用的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)

  • 具有鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)，所使用的物理存儲結(jié)構(gòu)是鏈?zhǔn)酱鎯?/p>

• 鏈表的分類：

  • 單向鏈表：單鏈表是一種最簡的鏈表，只有一個引用域¹next

    特點(diǎn)：通過next可以訪問到后繼結(jié)點(diǎn)，終端結(jié)點(diǎn)的引用域指向null

  • 雙向鏈表：具有兩個引用域prev和next，prev用來保存前驅(qū)結(jié)點(diǎn)的地址，next用來保存后繼結(jié)點(diǎn)的地址

    特點(diǎn)：通過next可以訪問后繼結(jié)點(diǎn)，終端結(jié)點(diǎn)的next指向null；通過prev可以訪問到前驅(qū)節(jié)點(diǎn)，起始結(jié)點(diǎn)的prev指向null

  • 循環(huán)鏈表：循環(huán)鏈表本質(zhì)是一種特殊的單向鏈表，只是它的終端結(jié)點(diǎn)指向了開始結(jié)點(diǎn)（也就是next存放了開始結(jié)點(diǎn)的地址）

    特點(diǎn)：所有結(jié)點(diǎn)都能具有前驅(qū)節(jié)點(diǎn)和后繼結(jié)點(diǎn)

• 鏈表的使用場景：對查找速度要求不高，但對插入和刪除速度要求高時，可以使用鏈表。常見的比如：

2、單向鏈表

單向鏈表（簡稱單鏈表）有帶頭結(jié)點(diǎn)的單鏈表，也有不帶頭鏈表的單鏈表。

• 單鏈表的基本操作：

  • 非空判斷：判斷鏈表中是否含有元素
  • 求表長度：獲取鏈表中所有元素的個數(shù)
  • 插入結(jié)點(diǎn)：在單鏈表中添加一個新的結(jié)點(diǎn)
  • 刪除結(jié)點(diǎn)：刪除單鏈表中的結(jié)點(diǎn)
  • 取表元素：更具所給索引，確定該索引所在鏈表的結(jié)點(diǎn)
  • 定位元素：根據(jù)所給值，確定該元素所在鏈表的索引號
  • 修改元素：根據(jù)所給索引，修改對應(yīng)的結(jié)點(diǎn)
  • 清空鏈表：清空鏈表中所有的元素

2.1 帶頭節(jié)點(diǎn)的單向鏈表

帶頭結(jié)點(diǎn)就是先固定一個頭節(jié)點(diǎn)，用來標(biāo)識鏈表的初始位置，它的data域不存任何東西，它的next域用來第一個結(jié)點(diǎn)的地址，每次遍歷鏈表或定位結(jié)點(diǎn)都需要借助一個輔助變量temp來實(shí)現(xiàn)。

• 插入結(jié)點(diǎn)示意圖：

  

• 刪除結(jié)點(diǎn)示意圖：

  

• 修改結(jié)點(diǎn)示意圖：

  

遍歷經(jīng)驗(yàn)總結(jié)：當(dāng)我們想要進(jìn)行的操作的結(jié)點(diǎn)依賴于前一個結(jié)點(diǎn)時，比如插入、刪除、修改等操作操作，就必須從head結(jié)點(diǎn)開始遍歷，否則會出現(xiàn)空指針異常；當(dāng)我們想要進(jìn)行的操作不依賴前一個結(jié)點(diǎn)時，就無須從head結(jié)點(diǎn)開始遍歷，比如根據(jù)id獲取結(jié)點(diǎn)，非空判斷、獲取鏈表長度、展示鏈表等操作。

測試類：

package com.hhxy.linkedlist;

import java.util.Scanner;

import com.hhxy.queue.ArrayQueue2;
/**
 * 單向鏈表測試類
 * @author ghp
 * 測試數(shù)據(jù)：
 * 1 宋江 及時雨
 * 2 林沖 豹子頭
 * 3 魯智深 花和尚
 * 4 吳用 智多星
 */
public class SingleLinkedListTest {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		SingleLinkedListDemo1 sll = new SingleLinkedListDemo1();//創(chuàng)建鏈表
		OUT:
		while(true) {
			System.out.println("-------------------單向鏈表操作界面-----------------");
			System.out.println("請輸入操作指令：");
			System.out.println("0 : 退出程序");
			System.out.println("1 : 在鏈尾添加結(jié)點(diǎn)");
			System.out.println("2 : 按id從小到大的順序添加結(jié)點(diǎn)");
			System.out.println("3 : 根據(jù)id獲取結(jié)點(diǎn)");
			System.out.println("4 : 根據(jù)id刪除結(jié)點(diǎn)");
			System.out.println("5 : 獲取鏈表中元素的個數(shù)");
			System.out.println("6 : 展示鏈表中所有的元素");
			System.out.println("7 : 根據(jù)id修改結(jié)點(diǎn)");
			System.out.println("8 : 清空鏈表");
			//用于接收用戶輸入
			int id;
			String name="";
			String alias="";
			Student student = null;
			switch(sc.next()) {
			case "0": //退出程序
				System.out.println("正在退出程序~~~");
				break OUT;
			case "1": //在鏈尾添加結(jié)點(diǎn)
				System.out.println("請按照 id name alias 的格式輸入要添加的元素：");
				id = sc.nextInt();
				name = sc.next();
				alias = sc.next();
				student = new Student(id,name,alias);
				if(sll.add(student)) System.out.println("結(jié)點(diǎn)："+student+"添加成功！");
				break;
			case "2"://按id從小到大的順序添加結(jié)點(diǎn)
				System.out.println("請按照 id name alias 的格式輸入要添加的元素：");
				id = sc.nextInt();
				name = sc.next();
				alias = sc.next();
				student = new Student(id,name,alias);
				if(sll.addById(student)) System.out.println("結(jié)點(diǎn)："+student+"添加成功！");
				break;
			case "3"://根據(jù)id獲取結(jié)點(diǎn)
				System.out.println("請輸入要獲取結(jié)點(diǎn)的id號：");
				id = sc.nextInt();
				try {
					student  = sll.get(id);
					System.out.println(id+"號結(jié)點(diǎn)為："+student);
				}catch(Exception e){
					System.out.println(e.getMessage());
				}
				break;
			case "4"://根據(jù)id刪除結(jié)點(diǎn)
				System.out.println("請輸入要刪除結(jié)點(diǎn)的id號：");
				id = sc.nextInt();
				try {
					if(sll.remove(id)) System.out.println("結(jié)點(diǎn)刪除成功！");
				}catch(Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case "5"://獲取鏈表中結(jié)點(diǎn)的個數(shù)（不包括頭節(jié)點(diǎn)）
				System.out.println("鏈表中的結(jié)點(diǎn)個數(shù)為："+sll.size());
				break;
			case "6"://展示鏈表中所有的結(jié)點(diǎn)（不包括頭節(jié)點(diǎn)）
				sll.show();
				break;
			case "7"://根據(jù)id修改結(jié)點(diǎn)
				System.out.println("請按照 id name alias 的格式輸入要修改的元素：");
				student = new Student(sc.nextInt(),sc.next(),sc.next());
				try {
					if(sll.update(student)) System.out.println("修改成功");
				}catch(Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case "8"://清空鏈表
				if(sll.clear()) System.out.println("鏈表已成功清空！");
				break;
			default:
				System.out.println("請輸入有效指令！");
				break;
			}
		}
		System.out.println("程序已退出");
	}
}

鏈表實(shí)現(xiàn)類：

package com.hhxy.linkedlist;

//結(jié)點(diǎn)類
class Student{
	//數(shù)據(jù)域（將成員變量設(shè)置為public方便外部訪問）
	public int id;
	public String name;
	public String alias;
	//引用域
	public Student next;
	
	public Student(int id, String name, String alias) {
		this.id = id;
		this.name = name;
		this.alias = alias;
	}

	@Override
	public String toString() {
		return "[id=" + id + ", name=" + name + ", alias=" + alias + "]";
	}
}

//鏈表類
public class SingleLinkedListDemo1 {
	//初始化頭結(jié)點(diǎn)
	Student head = new Student(-99,"","");
	/**
	 * 判斷鏈表是否為空
	 * @return true表示鏈表為空
	 */
	public boolean isEmpty() {
		//因?yàn)轭^節(jié)點(diǎn)是鏈表位置的標(biāo)識，不能動，所以使用一個輔助引用來遍歷鏈表
		Student temp = head.next;
		if(temp!=null) {
			//head后面存在至少一個元素，所以鏈表不為空
			return false;
		}
		return true;
	}
	/**
	 * 在鏈尾添加結(jié)點(diǎn)
	 * @param student 待添加的結(jié)點(diǎn)
	 * @return true表示添加成功
	 */
	public boolean add(Student student) {
		//同理，因?yàn)殒湵眍^節(jié)點(diǎn)不能動。
		//注意：需要是從頭節(jié)點(diǎn)開始遍歷，因?yàn)殒湵砜赡転榭?，如果從頭節(jié)點(diǎn)后一個遍歷，當(dāng)鏈表為空時會報空指針異常
		Student temp = head;
		//遍歷尋找尾結(jié)點(diǎn)。因?yàn)閠emp=head，所以是從頭節(jié)點(diǎn)開始遍歷
		while(temp.next != null) {
			temp = temp.next;
		}
		//已找到鏈表尾結(jié)點(diǎn)，進(jìn)行指向
		temp.next = student;
		return true;
	}
	/**
	 * 按照id從小到大的順序添加結(jié)點(diǎn)
	 * @param student 待添加的結(jié)點(diǎn)
	 * @return true表示添加成功
	 */
	public boolean addById(Student student) {
		Student temp = head;
		boolean flag = true;//用于判斷鏈表是加在尾結(jié)點(diǎn)，還是加在結(jié)點(diǎn)之間
		while(temp.next != null) {
			if(student.id < temp.next.id) {
				//說明是添加在結(jié)點(diǎn)之間
				flag = false;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果添加的結(jié)點(diǎn)是在尾結(jié)點(diǎn)
			temp.next = student;
		}else {
			//添加的結(jié)點(diǎn)是在結(jié)點(diǎn)之間
			student.next = temp.next;//切記：先改變后一個指向，再改變前一個指向
			temp.next = student;
		}
		return true;
	}
	/**
	 * 根據(jù)id獲取結(jié)點(diǎn)
	 * @param id 
	 * @return 返回對應(yīng)id的結(jié)點(diǎn)
	 */
	public Student get(int id) {
		if(isEmpty()) {
			throw new RuntimeException("該鏈表為空！");
		}
		Student temp = head.next;
		//從head結(jié)點(diǎn)后面開始遍歷
		boolean flag = false;//判斷鏈表中是否存在待獲取的結(jié)點(diǎn)
		while(temp != null) {
			if(temp.id == id) {
				//找到id對應(yīng)的結(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果找到id對應(yīng)結(jié)點(diǎn)
			return temp;
		}else {
			//如果沒有找到id對應(yīng)的結(jié)點(diǎn)
			throw new RuntimeException("待獲取的結(jié)點(diǎn)不存在！");
		}
	}
	/**
	 * 根據(jù)id刪除結(jié)點(diǎn)
	 * @param id 待刪除結(jié)點(diǎn)的id
	 * @return true表示刪除成功
	 */
	public boolean remove(int id) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		Student temp = head;//刪除結(jié)點(diǎn)需要依賴前一個結(jié)點(diǎn)，所以從頭節(jié)點(diǎn)開始遍歷
		boolean flag = false;//判斷鏈表中是否存在待刪除的結(jié)點(diǎn)
		while(temp.next != null) {
			if(temp.next.id == id) {
				//找到該結(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果找到了要刪除的結(jié)點(diǎn)
			temp.next = temp.next.next;
		}else {
			//如果沒有找到id對應(yīng)的結(jié)點(diǎn)
			throw new RuntimeException("待刪除的結(jié)點(diǎn)不存在！");
		}
		return true;
	}
	/**
	 * 獲取鏈表中結(jié)點(diǎn)的個數(shù)（不包括頭節(jié)點(diǎn)）
	 */
	public int size() {
		Student temp = head;
		int count = 0;
        //這里雖然遍歷了頭節(jié)點(diǎn)，但是沒有遍歷尾結(jié)點(diǎn)
		while(temp.next != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}
	/**
	 * 展示鏈表中所有的結(jié)點(diǎn)（不包括頭節(jié)點(diǎn)）
	 */
	public void show() {
		if(isEmpty()) {
			System.out.println("鏈表為空！");
			return;
		}
		//注意：不需要展示頭節(jié)點(diǎn)！
		Student temp = head;
		while(temp.next != null) {
			System.out.println(temp.next);
			temp = temp.next;
		}
	}
	/**
	 * 根據(jù)id修改結(jié)點(diǎn)
	 * @param student 待修改的結(jié)點(diǎn)
	 * @return true表示修改成功
	 */
	public boolean update(Student student) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		Student temp = head;
		boolean flag = false;//判斷鏈表是否修改成功
		while(temp.next != null) {
			if(temp.next.id == student.id) {
				//找到要修改的鏈表
				flag = true;
				student.next = temp.next.next;
				temp.next = student;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果修改成功
			return true;
		}else {
			//如果鏈表中沒有找到待刪除的結(jié)點(diǎn)
			throw new RuntimeException("鏈表中不存在該結(jié)點(diǎn)");
		}
	}
	/**
	 * 清空鏈表
	 * @return true表示清空成功
	 */
	public boolean clear() {
		/*方式一：直接將頭節(jié)點(diǎn)指向空(節(jié)約時間，但占內(nèi)存)
		 * head.next = null;
		 * 除頭節(jié)點(diǎn)以外其它結(jié)點(diǎn)存在引用，JVM不會回收結(jié)點(diǎn)內(nèi)存，仍然會占據(jù)內(nèi)存
		 * 這種清楚方法很費(fèi)內(nèi)存！ 
		 */
		//方式二：將所有結(jié)點(diǎn)占據(jù)的內(nèi)存都進(jìn)行釋放（耗時，但不占內(nèi)存）
		Student2 temp = head;//這里需要從后往前遍歷，逐步去掉所有結(jié)點(diǎn)的引用，否則無法遍歷下取
		while(head.next != null) {
			for (int i = size(); i > 1; i--) {
				temp = temp.next;
			}
			temp.next = null;
		}
		return true;
	}
}

2.2 不帶頭節(jié)點(diǎn)的單向鏈表

略……邏輯思路都差不多，只是將頭節(jié)點(diǎn)換成一個頭指針

不帶頭節(jié)點(diǎn)和帶頭結(jié)點(diǎn)的主要區(qū)別：帶頭結(jié)點(diǎn)遍歷的時候、不能將頭節(jié)點(diǎn)進(jìn)行計數(shù)；而不帶結(jié)點(diǎn)能夠直接進(jìn)行遍歷

本質(zhì)上兩者并沒有什么太大區(qū)別，帶頭節(jié)點(diǎn)的鏈表沒有指針，頭結(jié)點(diǎn)就相當(dāng)于頭指針，而不帶頭節(jié)點(diǎn)的鏈表是由頭指針的

注意：這里所謂的指針和結(jié)點(diǎn)其實(shí)都是結(jié)點(diǎn)對象，只是指針初始值為null，結(jié)點(diǎn)要進(jìn)行初始化

2.3 練習(xí)

• 反轉(zhuǎn)鏈表示意圖：

• 合并鏈表示意圖：

測試類：

/**
 * 練習(xí)題1：獲取鏈表倒數(shù)第k個結(jié)點(diǎn)
 * 練習(xí)題2：將鏈表反轉(zhuǎn)
 * 練習(xí)題3：從尾到頭打印鏈表的結(jié)點(diǎn)
 * 練習(xí)題4：合并兩個有序鏈表，合并后仍然有序
 */
//測試類：
public class SingleLinkedListDemo3{
	public static void main(String[] args) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		SingleLinkedList sll = new SingleLinkedList();
		sll.add(node1);
		sll.add(node2);
		sll.add(node3);
		System.out.println("鏈表原始狀態(tài)：");
		sll.show();
		
		System.out.println("------------------------");
		//測試1：測試獲取鏈表倒數(shù)第k個結(jié)點(diǎn)
		Node t = sll.findLastIndexNode(sll, 1);
		System.out.println(sll.findLastIndexNode(sll,1));
		System.out.println(sll.findLastIndexNode(sll,2));
		System.out.println(sll.findLastIndexNode(sll,3));
		
		System.out.println("-------------------------");
		//測試2：測試將鏈表反轉(zhuǎn)
		sll.reverset(sll);
		System.out.println("反轉(zhuǎn)后的鏈表：");
		sll.show();
		
		System.out.println("-------------------------");
		//測試3：從頭到位打印鏈表
		System.out.println("反向打印鏈表：");
		sll.reversetPrint(sll);
		
		System.out.println("-------------------------");
		//測試4：將兩個有序鏈表合并，合并后仍然有序
		SingleLinkedList list1 = new SingleLinkedList();
		SingleLinkedList list2 = new SingleLinkedList();
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		Node node9 = new Node(9);
		Node node10 = new Node(10);
		Node node11 = new Node(11);
		
		list1.add(node4);
		list1.add(node7);
		list1.add(node8);
		list1.add(node10);
		list1.add(node11);
		System.out.println("鏈表1：");
		list1.show();
		
		System.out.println("鏈表2：");
		list2.add(node5);
		list2.add(node6);
		list2.add(node9);
		list2.show();
		
		SingleLinkedList list = new SingleLinkedList();
		list = list.combine(list1, list2);
		
		System.out.println("合并后的鏈表：");
		list.show();
	}
}

鏈表實(shí)現(xiàn)類：

package com.hhxy.linkedlist;

import java.util.Stack;

//結(jié)點(diǎn)類
class Node {
	int n;
	Node next;
	public Node(int n) {
		this.n = n;
	}
	@Override
	public String toString() {
		return "[n=" + n + "]";
	}
}
//鏈表類：
public class SingleLinkedList {
	//初始化頭節(jié)點(diǎn)
	public Node head = new Node(-99);
	/**
	 * 添加結(jié)點(diǎn)
	 */
	public void add(Node node) {
		Node current = head;
		while(current.next != null) {
			current = current.next;
		}
		current.next = node;
	}
	/**
	 * 獲取鏈表的長度
	 * @return
	 */
	public int size() {
		Node current = head.next;
		int count = 0;
		while(current != null) {
			count++;
			current = current.next;
		}
		return count;
	}
	/**
	 * 展示
	 */
	public void show() {
		Node current = head.next;
		while(current != null) {
			System.out.println(current);
			current = current.next;
		}	
	}
	/*--------------------核心方法-------------------------*/
	/**
	 * 尋找鏈表倒數(shù)第k個結(jié)點(diǎn)
	 * @param index
	 * @return
	 */
	public Node findLastIndexNode(SingleLinkedList sll,int index) {
		Node head = sll.head;
		if(index <0 || index>sll.size() || head.next == null) {
			return null;
		}
		Node current = head.next;
		//將指針從第二個結(jié)點(diǎn)開始往后移動index位
		for (int i = 0; i < size()-index; i++) {
			current = current.next;
		}
		return current;
	}
	/**
	 * 將鏈表反轉(zhuǎn)
	 * @param sll 待反轉(zhuǎn)的鏈表
	 */
	public void reverset(SingleLinkedList sll) {
		Node head = sll.head;
		if(head.next == null || head.next.next == null) {
			//當(dāng)前鏈表為空，或者只有一個結(jié)點(diǎn)，直接返回
			return;
		}
		SingleLinkedList sllTemp = new SingleLinkedList();//創(chuàng)建一個新鏈表
		Node headTemp = sllTemp.head;
		Node temp = null;//用來存舊鏈表的引用，方便遍歷舊鏈表
		Node current = head.next;//輔助遍歷舊鏈表
		while(current != null) {
			temp = current.next;//不保存，新鏈表就會斷開，就無法進(jìn)行遍歷了
			current.next = headTemp.next;//指向新創(chuàng)建的頭結(jié)點(diǎn)的后面的結(jié)點(diǎn)
			headTemp.next = current;//新創(chuàng)建的頭結(jié)點(diǎn)，指向插入的結(jié)點(diǎn)
			current = temp;//指針往后移
		}
		head.next = headTemp.next;
	}
	/**
	 * 反向打印鏈表
	 * @param sll
	 */
	public void reversetPrint(SingleLinkedList sll) {
		Node head = sll.head;
		if(head.next == null) {
			return;
		}
	/*
	  //方式一：使用findLastIndexNode方法（要先實(shí)現(xiàn)findLastIndexNode方法，不值得推薦）
		for(int i=1;i<=sll.size();i++) {
			System.out.println(sll.findLastIndexNode(sll, i));
		}
	  //方式二：使用reverset方法（要先實(shí)現(xiàn)reverset方法，并且改變了鏈表的結(jié)構(gòu)，不值得推薦）
	    reverset(sll);
	    sll.show();
	*/
		//方式三：使用棧（強(qiáng)烈推薦）
		Stack<Node> stack = new Stack<>();
		Node current = head.next;
		while(current != null) {
			stack.push(current);
			current = current.next;
		}
		while(stack.size()>0) {
			System.out.println(stack.pop());
		}
	}
	/**
	 * 合并兩個有序鏈表，合并后仍然有序(這里我是默認(rèn)按從小到大排序的)
	 */
	public SingleLinkedList combine(SingleLinkedList sll1,SingleLinkedList sll2) {
		Node head1 = sll1.head.next;//用于遍歷sll1鏈表
		Node head2 = sll2.head.next;
		if(head1 == null || head2  == null) {
        	//只要有一個鏈表為空就直接返回
        	return head1 != null ? sll1 : sll2;
        }
		SingleLinkedList sll = new SingleLinkedList();//合并后的鏈表
        Node temp=sll.head;//用來給sll鏈表添加結(jié)點(diǎn)的
        while (head1 != null && head2 != null){
            if (head1.n < head2.n){
            	//鏈表1的結(jié)點(diǎn)是當(dāng)前最小結(jié)點(diǎn)
                temp.next = head1;//新鏈表連接最小結(jié)點(diǎn)
                temp = temp.next;//每新增一個結(jié)點(diǎn)，temp就往后移一位，保證他在尾結(jié)點(diǎn)方便連接新結(jié)點(diǎn)
                head1 = head1.next;//鏈表1的指針也往后移一位
            }else{
            	//鏈表2的結(jié)點(diǎn)是當(dāng)前最小結(jié)點(diǎn)
                temp.next = head2;
                temp = temp.next;
                head2 = head2.next;
            }
        }
        if (head1 != null && head2 == null){
        	//經(jīng)過一一段時間的合并后，sll2的鏈表為空了，直接就將sll1鏈表后面的結(jié)點(diǎn)拼接上去
            temp.next = head1;
        }
        if (head1 == null && head2 != null){
            temp.next = head2;
        }
        return sll;
    }
	/*------------------------------------------------*/
}

3、雙向鏈表

雙向鏈表相對單向鏈表就較為簡單了，因?yàn)槊總€結(jié)點(diǎn)既能往后遍歷，又能往前遍歷 ，對于插入、刪除、修改都無需像單鏈表一樣依靠前一個結(jié)點(diǎn)。

與單鏈表的主要區(qū)別：

1. 遍歷不僅可以往前遍歷，還可以往后遍歷

2. 插入、刪除、修改不需要依賴前一個結(jié)點(diǎn)（在鏈尾插入需要依賴尾結(jié)點(diǎn)）

3. 添加的時候，需要進(jìn)行雙向綁定！

• 雙向鏈表插入示意圖：

  

  

• 雙向鏈表刪除示意圖：

  

  

測試類：

和單向鏈表的測試方法相同

示意圖：

雙向鏈表實(shí)現(xiàn)類：

其實(shí)只要理解了單向鏈表，再來看雙向鏈表就會覺得so easy??單向鏈表的方法雙向鏈表都能使用，只是添加和修改的時候，需要多修改下prev的的指向。

package com.hhxy.linkedlist.doubles;
//結(jié)點(diǎn)類
class Student2{
	public int id;
	public String name;
	public String alias;
	public Student2 prev;//指向前一個結(jié)點(diǎn)
	public Student2 next;//指向后一個結(jié)點(diǎn)
	
	public Student2(int id, String name, String alias) {
		super();
		this.id = id;
		this.name = name;
		this.alias = alias;
	}
	@Override
	public String toString() {
		return "Student [n=" + id + ", name=" + name + ", alias=" + alias + "]";
	}
}
//鏈表類
public class DoubleLinkedListDemo1 {
	//初始化頭節(jié)點(diǎn)
	public Student2 head = new Student2(-99,"","");
	/**
	 * 判斷鏈表是否為空
	 * @return true表示鏈表為空
	 */
	public boolean isEmpty() {
		//因?yàn)轭^節(jié)點(diǎn)是鏈表位置的標(biāo)識，不能動，所以使用一個輔助引用來遍歷鏈表
		 Student2 temp = head.next;
		if(temp!=null) {
			//head后面存在至少一個元素，所以鏈表不為空
			return false;
		}
		return true;
	}
	/**
	 * 在鏈尾添加結(jié)點(diǎn)
	 * @param student2 待添加的結(jié)點(diǎn)
	 * @return true表示添加成功
	 */
	public boolean add(Student2 student2) {
		//同理，因?yàn)殒湵眍^節(jié)點(diǎn)不能動。
		//注意：需要是從頭節(jié)點(diǎn)開始遍歷，因?yàn)殒湵砜赡転榭?，如果從頭節(jié)點(diǎn)后一個遍歷，當(dāng)鏈表為空時會報空指針異常
		Student2 temp = head;
		//遍歷尋找尾結(jié)點(diǎn)。因?yàn)閠emp=head，所以是從頭節(jié)點(diǎn)開始遍歷
		while(temp.next != null) {
			temp = temp.next;
		}
		//形成雙向鏈表
		temp.next = student2;
		student2.prev = temp;
		return true;
	}
	/**
	 * 按照id從小到大的順序添加結(jié)點(diǎn)
	 * @param student2 待添加的結(jié)點(diǎn)
	 * @return true表示添加成功
	 */
	public boolean addById(Student2 student2) {
		Student2 temp = head;
		boolean flag = true;//用于判斷鏈表是加在尾結(jié)點(diǎn)，還是加在結(jié)點(diǎn)之間
		while(temp.next != null) {
			if(student2.id < temp.next.id) {
				//說明是添加在結(jié)點(diǎn)之間
				flag = false;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果添加的結(jié)點(diǎn)是在尾結(jié)點(diǎn)
			//形成雙向鏈表
			temp.next = student2;
			student2.prev = temp;
		}else {
			//添加的結(jié)點(diǎn)是在結(jié)點(diǎn)之間，注意要形成雙向指向
			student2.next = temp.next;//切記：先改變后一個指向，再改變前一個指向
			temp.next.prev = student2;
			//前面一根線
			temp.next = student2;
			student2.prev = temp;
		}
		return true;
	}
	/**
	 * 根據(jù)id獲取結(jié)點(diǎn)
	 * @param id 
	 * @return 返回對應(yīng)id的結(jié)點(diǎn)
	 */
	public Student2 get(int id) {
		if(isEmpty()) {
			throw new RuntimeException("該鏈表為空！");
		}
		Student2 temp = head.next;
		//從head結(jié)點(diǎn)后面開始遍歷
		boolean flag = false;//判斷鏈表中是否存在待獲取的結(jié)點(diǎn)
		while(temp != null) {
			if(temp.id == id) {
				//找到id對應(yīng)的結(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果找到id對應(yīng)結(jié)點(diǎn)
			return temp;
		}else {
			//如果沒有找到id對應(yīng)的結(jié)點(diǎn)
			throw new RuntimeException("待獲取的結(jié)點(diǎn)不存在！");
		}
	}
	/**
	 * 根據(jù)id刪除結(jié)點(diǎn)
	 * @param id 待刪除結(jié)點(diǎn)的id
	 * @return true表示刪除成功
	 */
	public boolean remove(int id) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		//使用雙向鏈表可以進(jìn)行自我刪除
		Student2 temp = head.next;//刪除結(jié)點(diǎn)需要依賴前一個結(jié)點(diǎn)，所以從頭節(jié)點(diǎn)開始遍歷
		boolean flag = false;//判斷鏈表中是否存在待刪除的結(jié)點(diǎn)
		while(temp != null) {
			if(temp.id == id) {
				//找到該結(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果找到了要刪除的結(jié)點(diǎn)
			temp.prev.next = temp.next;//前一根線
			if(temp.next != null) {//要排除最后一個結(jié)點(diǎn)的可能，否則會出現(xiàn)空指針異常
				temp.next.prev = temp.prev;//后一根線
			}
		}else {
			//如果沒有找到id對應(yīng)的結(jié)點(diǎn)
			throw new RuntimeException("待刪除的結(jié)點(diǎn)不存在！");
		}
		return true;
	}
	/**
	 * 獲取鏈表中結(jié)點(diǎn)的個數(shù)
	 * @return
	 */
	public int size() {
		Student2 temp = head;
		int count = 0;
		while(temp.next != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}
	/**
	 * 展示鏈表中所有的結(jié)點(diǎn)
	 */
	public void show() {
		if(isEmpty()) {
			System.out.println("鏈表為空！");
			return;
		}
		Student2 temp = head;
		while(temp.next != null) {
			System.out.println(temp.next);
			temp = temp.next;
		}
	}
	/**
	 * 根據(jù)id修改結(jié)點(diǎn)
	 * @param student2 待修改的結(jié)點(diǎn)
	 * @return true表示修改成功
	 */
	public boolean update(Student2 student2) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		Student2 temp = head.next;
		boolean flag = false;//判斷鏈表是否修改成功
		while(temp != null) {
			if(temp.id == student2.id) {
				//找到要修改的鏈表
				flag = true;
				//后一根線
				student2.next = temp.next;
				if(temp.next!=null) {
					//排除最后一個節(jié)點(diǎn)
					temp.next.prev = student2;
				}
				//前一根線
				temp.prev.next = student2;
				student2.prev = temp.prev;
			
				
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			//如果修改成功
			return true;
		}else {
			//如果鏈表中沒有找到待刪除的結(jié)點(diǎn)
			throw new RuntimeException("鏈表中不存在該結(jié)點(diǎn)");
		}
	}
	/**
	 * 清空鏈表
	 * @return
	 */
	public boolean clear() {
		/*方式一：直接將頭節(jié)點(diǎn)指向空(節(jié)約時間，但占內(nèi)存)
		 * head.next = null;
		 * 除頭節(jié)點(diǎn)以外其它結(jié)點(diǎn)存在引用，JVM不會回收結(jié)點(diǎn)內(nèi)存，仍然會占據(jù)內(nèi)存
		 * 這種清楚方法很費(fèi)內(nèi)存！ 
		 * return true;
		 */
		//方式二：將所有結(jié)點(diǎn)占據(jù)的內(nèi)存都進(jìn)行釋放（耗時，但不占內(nèi)存）
		Student2 temp = head;//這里需要從后往前遍歷，逐步去掉所有結(jié)點(diǎn)的引用，否則無法遍歷下取
		Student2 current = head;
		while(current.next != null) {
			current = temp;
			current.next = null;
			current.prev = null;
			temp = temp.next;
		}
		return true;
	}
}

4、單向環(huán)形鏈表

基本和單向鏈表類似，也可以分為帶頭節(jié)點(diǎn)，和不帶頭結(jié)點(diǎn)點(diǎn)，這里演示的是不帶頭結(jié)點(diǎn)的單向環(huán)形鏈表，單向環(huán)形鏈表和單向鏈表唯一的區(qū)別：尾結(jié)點(diǎn)的next不指向空，而是指向開始節(jié)點(diǎn)。

主要思想還是在單鏈表那一節(jié)??只要掌握單向鏈表，這些雙向鏈表還有單向循環(huán)鏈表就是弟弟(′д｀ )…彡…彡直接套用第一節(jié)的接口，實(shí)現(xiàn)所有的方法

測試類：

和2.1一樣，換個對象就行了（這個測試類真渣??）

實(shí)現(xiàn)類：

這里主要記錄以下按順序插入結(jié)點(diǎn)的思路，怕以后忘記了。其實(shí)主要思想還是和單向鏈表的addById方法的邏輯是一致的，主要是要考慮循環(huán)！思路主要如下：

1. 先將鏈表添加分為兩大類，首結(jié)點(diǎn)的添加 和 非首結(jié)點(diǎn)的添加，因?yàn)槭捉Y(jié)點(diǎn)的添加需要自動成環(huán)
2. 再將非首結(jié)點(diǎn)的添加又分為在 添加在首結(jié)點(diǎn)之前 和 之后，之前需要移動first指針，之后不需要移動

示意圖：

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

1. 先將刪除分為兩大類，刪除頭結(jié)點(diǎn) 和 刪除普通結(jié)點(diǎn)
2. 刪除頭結(jié)點(diǎn)又可以分為兩類，鏈表只有一個頭結(jié)點(diǎn) 和 除了頭結(jié)點(diǎn)還有其它結(jié)點(diǎn)
3. 刪除普通結(jié)點(diǎn)時需要注意鏈表是單向的，刪除操作需要依賴待刪除結(jié)點(diǎn)的前一個結(jié)點(diǎn)

修改結(jié)點(diǎn)的邏輯思路和刪除類似，不在贅述，示意圖：

• 清空鏈表：鏈表的清空有兩種方法，一種是直接讓first=null，這種清空簡單省事，但是是假清空，鏈表仍然存在內(nèi)存中！

  第二種方法是讓每個結(jié)點(diǎn)的next指向空，然后將first=null，這種費(fèi)腦子但是省空間

package com.hhxy.linkedlist.circular;


//結(jié)點(diǎn)類
class Student{
	public int id;
	public String name;
	public String alias;
	public Student next;
	
	public Student(int id, String name, String alias) {
		super();
		this.id = id;
		this.name = name;
		this.alias = alias;
	}

	@Override
	public String toString() {
		return "[id=" + id + ", name=" + name + ", alias=" + alias + "]";
	}
}

//鏈表類
public class CircularLinkedListDemo1 {
	private Student first = null;//注意這是頭指針，不是頭結(jié)點(diǎn)！
	
	/**
	 * 非空判斷
	 * @return true表示為空
	 */
	public boolean isEmpty() {
		//因?yàn)槭菦]有頭結(jié)點(diǎn)，所以直接判斷first
		if(first != null) {
			return false;
		}else {
			return true;
		}
	}
	/**
	 * 在尾結(jié)點(diǎn)添加結(jié)點(diǎn)
	 * @param student
	 * @return true表示結(jié)點(diǎn)添加成功
	 */
	public boolean add(Student student) {
		if(first == null) {
			//對第一個結(jié)點(diǎn)進(jìn)行單獨(dú)考慮
			first =  student;
			first.next = first;//構(gòu)成環(huán)狀
			return true;
		}else {
			Student current = first;
			//找到最后一個結(jié)點(diǎn)
			while(current.next != first) {
				current = current.next;
			}
			//找到后將節(jié)點(diǎn)加入環(huán)形鏈表中
			current.next = student;
			student.next = first;
			return true;
		}
	}
	/**
	 * 根據(jù)id從小到大的順序添加結(jié)點(diǎn)
	 * @return true表示添加成功
	 */
	public boolean addById(Student student) {
		if(first == null) {
			//第一個結(jié)點(diǎn)單獨(dú)成環(huán)
			first = student;
			first.next = first;
		}else {
			Student current = first;
			if(student.id < current.id && current == first) {
				//說明這個結(jié)點(diǎn)比頭結(jié)點(diǎn)還要小，要將頭指針移動位置
				current.next = student;
				student.next = current;
				first = student;//將first移動到student上
				return true;
			}
			while(current.next != first) {
				//尋早結(jié)點(diǎn)添加的位置
				if(student.id < current.next.id) {
					//已找到添加的位置
					break;
				}
				current = current.next;
			}
			student.next = current.next;//切記：一定要先改變后一根線，不然鏈表會斷裂！
			current.next = student;
		}
		return true;
	}
	/**
	 * 根據(jù)id獲取結(jié)點(diǎn)
	 */
	public Student get(int id) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		Student current = first;
		boolean flag = false;
		while(true) {
			if(current.id == id) {
				//找到就直接結(jié)束遍歷
				flag = true;
				break;
			}
			if(current.next == first) {
				//如果是最后一個結(jié)點(diǎn)，就表明還沒有找到，直接結(jié)束遍歷
				break;
			}
			current = current.next;//輔助指針后移，遍歷鏈表
		}
		if(flag) {
			//找到就返回這個結(jié)點(diǎn)
			return current;
		}else {
			//沒有找到，打印提示信息
			throw new RuntimeException("鏈表中不存在該結(jié)點(diǎn)！");
		}
	}
	/**
	 * 根據(jù)id刪除結(jié)點(diǎn)
	 */
	public boolean remove(int id) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		if(first.id == id) {
			//當(dāng)頭結(jié)點(diǎn)就是要刪除的結(jié)點(diǎn)時，分類討論
			if(first.next == first) {
				//如果鏈表只有頭結(jié)點(diǎn)時
				first = null;
				return true;
			}else {
				//如果鏈表除了頭結(jié)點(diǎn)還有其它結(jié)點(diǎn)時，需要移動first指針
				Student current = first;
				//找到尾結(jié)點(diǎn)
				while(current.next != first) {
					current = current.next;
				}
				current.next = current.next.next;
				first = current.next;//移動頭指針
				return true;
			}
		}
		//刪除普通結(jié)點(diǎn)
		Student current = first;
		boolean flag = false;//判斷鏈表中是否存在該結(jié)點(diǎn)
		while(true) {
			if(current.next.id == id) {//這里使用current.next判斷是為了使用前一個結(jié)點(diǎn)
				//找到結(jié)點(diǎn)直接退出
				flag = true;
				break;
			}
			if(current.next == first) {
				//遍歷完成，直接退出
				break;
			}
			current = current.next;
		}
		if(flag) {
			//找到待刪除的結(jié)點(diǎn)，利用前一個結(jié)點(diǎn)將其刪除（思路和單項(xiàng)鏈表是一樣的）
			current.next = current.next.next;
			return true;
		}else {
			throw new RuntimeException("該結(jié)點(diǎn)不存在！");
		}
	}
	/**
	 * 獲取鏈表長度
	 */
	public int size() {
		Student current = first;
		if(isEmpty()) {
			return 0;//這里要不要都無所謂，只是習(xí)慣了~~~
		}
		int count = 0;
		while(true) {
			count++;
			if(current.next == first) {
				break;
			}
			current = current.next;
		}
		return count;
	}
	/**
	 * 展示鏈表
	 */
	public void show() {
		Student current = first;
		if(first == null) {
			//排除空鏈表
			throw new RuntimeException("鏈表為空！");
		}
		while(true) {
			System.out.println(current);
			if(current.next == first) {
				//當(dāng)發(fā)現(xiàn)結(jié)點(diǎn)是最后一個結(jié)點(diǎn)直接退出打印
				break;
			}
			current = current.next;
		}
	}
	/**
	 * 根據(jù)id修改結(jié)點(diǎn)
	 */
	public boolean update(Student student) {
		if(isEmpty()) {
			throw new RuntimeException("鏈表為空！");
		}
		if(student.id == first.id) {
			//修改的結(jié)點(diǎn)是頭節(jié)點(diǎn)
			if(first.next == first) {
				//只有一個頭節(jié)點(diǎn)
				first = student;
				first.next = student;
				return true;
			}else {
				//除了頭節(jié)點(diǎn)還有其它結(jié)點(diǎn)
				Student current = first;
				//找到尾結(jié)點(diǎn)
				while(current.next != first) {
					current = current.next;
				}
				student.next = current.next.next;//修改后一根線
				current.next = student;//修改前一根線
				first = student;//修改頭指針
				return true;
			}
		}
		//修改的結(jié)點(diǎn)是普通結(jié)點(diǎn)
		Student current = first;
		boolean flag = false;//判斷鏈表中是否存在該結(jié)點(diǎn)
		while(current.next != first) {
			if(current.next.id == student.id) {
				//找到結(jié)點(diǎn)，直接退出
				flag = true;
				break;
			}
			current = current.next;
		}
		if(flag) {
			student.next = current.next.next;//修改后一根線，防止鏈表斷裂
			current.next = student;
			return true;
		}else {
			throw new RuntimeException("不存在該結(jié)點(diǎn)！");
		}
	}
	/**
	 * 	清空鏈表
	 */
	public boolean clear() {
		/*方式一：直接將頭節(jié)點(diǎn)指向空(節(jié)約時間，但占內(nèi)存)
		 * first.next = null;
		 * 除頭節(jié)點(diǎn)以外其它結(jié)點(diǎn)存在引用，JVM不會回收結(jié)點(diǎn)內(nèi)存，仍然會占據(jù)內(nèi)存
		 * 這種清楚方法很費(fèi)內(nèi)存！ 
		 * return true;
		 */
		//方式二：將所有結(jié)點(diǎn)占據(jù)的內(nèi)存都進(jìn)行釋放（耗時，但不占內(nèi)存）
		if(isEmpty()) {
			return true;
		}
		if(first == first.next) {
			//只有一個結(jié)點(diǎn)
			first = null;
			return true;
		}
		Student temp = first;//臨時存儲current的引用，輔助遍歷
		Student current = first;
		//將鏈表每個結(jié)點(diǎn)的引用都斷開，這樣每個結(jié)點(diǎn)都沒有被引用，就能被JVM給回收
		while(current.next != first) {
			temp = temp.next;
			current.next = null;
			current = temp;
		}
		//將最后一個結(jié)點(diǎn)的引用 和頭指針 設(shè)為空
		current.next = null;//不斷開最后一個接待你的引用，頭節(jié)點(diǎn)就不會被回收
		first = null;
		return true;
	}
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)篇】手寫雙向鏈表、單向鏈表（超詳細(xì)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！