Java?數(shù)據(jù)結(jié)構(gòu)與算法系列精講之單向鏈表
概述
從今天開始, 小白我將帶大家開啟 Jave 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.
鏈表
鏈表 (Linked List) 是一種遞歸的動態(tài)數(shù)據(jù)結(jié)構(gòu). 鏈表以線性表的形式, 在每一個節(jié)點存放下一個節(jié)點的指針. 鏈表解決了數(shù)組需要先知道數(shù)據(jù)大小的缺點, 增加了節(jié)點的指針域, 空間開銷較大.
鏈表包括三類:
- 單向鏈表
- 雙向鏈表
- 循環(huán)鏈表
單向鏈表
單向鏈表 (Single Linked List) 是鏈表中最簡單的一種形式. 單向鏈表每個節(jié)點包含兩個部分, 第一部分是信息, 第二部分是下一個節(jié)點. (元素 + 指針)
單向鏈表實現(xiàn)
Node 類
// Node類 private class Node { public E e; // 元素 private SingleLinkedList.Node next; // 下一個節(jié)點 // 構(gòu)造 public Node(E e) { this.e = e; this.next = null; } @Override public String toString() { return e.toString(); } }
add 方法
// 添加數(shù)據(jù) public void add(int index, E e) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 SingleLinkedList.Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // 添加數(shù)據(jù) SingleLinkedList.Node node = new SingleLinkedList.Node(e); node.next = prev.next; prev.next = node; size++; }
remove 方法
// 刪除數(shù)據(jù) public void remove(int index) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // 刪除數(shù)據(jù) Node retNode = prev.next; prev.next = retNode.next; size --; }
get 方法
// 通過索引獲取鏈表數(shù)數(shù)據(jù) public E get(int index) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.e; }
set 方法
// 通過索引設(shè)置鏈表數(shù)據(jù) public E set(int index,E e) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } // 設(shè)置新值 cur.e = e; return cur.e; }
contain 方法
// 鏈表是否包含元素 public boolean contains(E e) { Node cur = dummyHead.next; // 遍歷所有節(jié)點 while (cur != null) { if (cur.e.equals(e)) { return true; } cur = cur.next; } return false; }
main
// main public static void main(String[] args) { // 創(chuàng)建單向鏈表 SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>(); // 添加數(shù)據(jù) for (int i = 0; i < 8; i++) { singleLinkedList.addFirst(i); System.out.println(singleLinkedList); } // 是否包含元素 System.out.println(singleLinkedList.contains(0)); System.out.println(singleLinkedList.contains(10)); // set singleLinkedList.set(0, 9); singleLinkedList.set(1, 7); System.out.println(singleLinkedList); // 刪除數(shù)據(jù) for (int i = 0; i < 8; i++) { singleLinkedList.remove(0); System.out.println(singleLinkedList); } }
輸出結(jié)果:
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
6->5->4->3->2->1->0->NULL
7->6->5->4->3->2->1->0->NULL
true
false
9->7->5->4->3->2->1->0->NULL
7->5->4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL
完整代碼
public class SingleLinkedList<E> { private Node dummyHead; // 頭指針 private int size; // 鏈表大小 // Node類 private class Node { public E e; // 元素 private Node next; // 下一個節(jié)點 // 構(gòu)造 public Node(E e) { this.e = e; this.next = null; } @Override public String toString() { return e.toString(); } } // 構(gòu)造 public SingleLinkedList() { dummyHead = new Node(null); size = 0; } // 表首添加元素 public void addFirst(E e) { add(0, e); } // 表尾添加元素 public void addLast(E e){ add(size, e); } // 添加數(shù)據(jù) public void add(int index, E e) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // 添加數(shù)據(jù) Node node = new Node(e); node.next = prev.next; prev.next = node; size ++; } // 刪除數(shù)據(jù) public void remove(int index) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // 刪除數(shù)據(jù) Node retNode = prev.next; prev.next = retNode.next; size --; } // 通過索引獲取鏈表數(shù)數(shù)據(jù) public E get(int index) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.e; } // 通過索引設(shè)置鏈表數(shù)據(jù) public E set(int index,E e) { // 檢查索引是否越界 if (index < 0 || index > size) { throw new RuntimeException("Invalid Index"); } // 獲取index前一個節(jié)點 Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } // 設(shè)置新值 cur.e = e; return cur.e; } // 鏈表是否包含元素 public boolean contains(E e) { Node cur = dummyHead.next; // 遍歷所有節(jié)點 while (cur != null) { if (cur.e.equals(e)) { return true; } cur = cur.next; } return false; } // 獲取鏈表大小 public int getSize() { return size; } // 判斷鏈表是否為空 public boolean isEmpty() { return size == 0; } @Override public String toString() { StringBuilder builder = new StringBuilder(); Node cur = dummyHead.next; while (cur != null) { builder.append(cur + "->"); cur = cur.next; } builder.append("NULL"); return builder.toString(); } // main public static void main(String[] args) { // 創(chuàng)建單向鏈表 SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>(); // 添加數(shù)據(jù) for (int i = 0; i < 8; i++) { singleLinkedList.addFirst(i); System.out.println(singleLinkedList); } // 是否包含元素 System.out.println(singleLinkedList.contains(0)); System.out.println(singleLinkedList.contains(10)); // set singleLinkedList.set(0, 9); singleLinkedList.set(1, 7); System.out.println(singleLinkedList); // 刪除數(shù)據(jù) for (int i = 0; i < 8; i++) { singleLinkedList.remove(0); System.out.println(singleLinkedList); } } }
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之單向鏈表的文章就介紹到這了,更多相關(guān)Java 單向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):單鏈表與雙向鏈表
- Java數(shù)據(jù)結(jié)構(gòu)之順序表和鏈表精解
- Java 數(shù)據(jù)結(jié)構(gòu)之刪除鏈表中重復(fù)的結(jié)點
- Java實現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的方法
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之環(huán)形鏈表
- Java?精煉解讀數(shù)據(jù)結(jié)構(gòu)的鏈表的概念與實現(xiàn)
- Java數(shù)據(jù)結(jié)構(gòu)之雙向鏈表圖解
- Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡單使用方法解析
相關(guān)文章
SpringCloud環(huán)境搭建過程之Rest使用小結(jié)
這篇文章主要介紹了SpringCloud環(huán)境搭建之Rest使用,本文通過實例代碼圖文相結(jié)合給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-08-08IDEA使用SequenceDiagram插件繪制時序圖的方法
這篇文章主要介紹了IDEA使用SequenceDiagram插件繪制時序圖的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09Spring MVC溫故而知新系列教程之請求映射RequestMapping注解
這篇文章主要介紹了Spring MVC溫故而知新系列教程之請求映射RequestMapping注解的相關(guān)知識,文中給大家介紹了RequestMapping注解提供的幾個屬性及注解說明,感興趣的朋友跟隨腳本之家小編一起學(xué)習(xí)吧2018-05-05