Java?數據結構與算法系列精講之單向鏈表
更新時間：2022年02月18日 10:59:12 作者：我是小白呀
單向鏈表特點是鏈表的鏈接方向是單向的，訪問要通過順序讀取從頭部開始。鏈表是使用指針構造的列表，是由一個個結點組裝起來的，又稱為結點列表。其中每個結點都有指針成員變量指向列表中的下一個結點，head指針指向第一個結點稱為表頭，而終止于最后一個指向nuLL的指針
概述
從今天開始, 小白我將帶大家開啟 Jave 數據結構 & 算法的新篇章.
鏈表
鏈表 (Linked List) 是一種遞歸的動態(tài)數據結構. 鏈表以線性表的形式, 在每一個節(jié)點存放下一個節(jié)點的指針. 鏈表解決了數組需要先知道數據大小的缺點, 增加了節(jié)點的指針域, 空間開銷較大.
鏈表包括三類:
- 單向鏈表
- 雙向鏈表
- 循環(huán)鏈表
單向鏈表
單向鏈表 (Single Linked List) 是鏈表中最簡單的一種形式. 單向鏈表每個節(jié)點包含兩個部分, 第一部分是信息, 第二部分是下一個節(jié)點. (元素 + 指針)
單向鏈表實現
Node 類
// Node類
private class Node {
public E e; // 元素
private SingleLinkedList.Node next; // 下一個節(jié)點
// 構造
public Node(E e) {
this.e = e;
this.next = null;
}
@Override
public String toString() {
return e.toString();
}
}
add 方法
// 添加數據
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;
}
// 添加數據
SingleLinkedList.Node node = new SingleLinkedList.Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
remove 方法
// 刪除數據
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;
}
// 刪除數據
Node retNode = prev.next;
prev.next = retNode.next;
size --;
}
get 方法
// 通過索引獲取鏈表數數據
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 方法
// 通過索引設置鏈表數據
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;
}
// 設置新值
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<>();
// 添加數據
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);
// 刪除數據
for (int i = 0; i < 8; i++) {
singleLinkedList.remove(0);
System.out.println(singleLinkedList);
}
}
輸出結果:
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é)點
// 構造
public Node(E e) {
this.e = e;
this.next = null;
}
@Override
public String toString() {
return e.toString();
}
}
// 構造
public SingleLinkedList() {
dummyHead = new Node(null);
size = 0;
}
// 表首添加元素
public void addFirst(E e) {
add(0, e);
}
// 表尾添加元素
public void addLast(E e){
add(size, e);
}
// 添加數據
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;
}
// 添加數據
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size ++;
}
// 刪除數據
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;
}
// 刪除數據
Node retNode = prev.next;
prev.next = retNode.next;
size --;
}
// 通過索引獲取鏈表數數據
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;
}
// 通過索引設置鏈表數據
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;
}
// 設置新值
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<>();
// 添加數據
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);
// 刪除數據
for (int i = 0; i < 8; i++) {
singleLinkedList.remove(0);
System.out.println(singleLinkedList);
}
}
}
到此這篇關于Java 數據結構與算法系列精講之單向鏈表的文章就介紹到這了,更多相關Java 單向鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Java AES加密和解密的相關資料，幫助大家更好的理解和學習Java，感興趣的朋友可以了解下2020-12-12
中國象棋是起源于中國的一種棋，屬于二人對抗性游戲的一種，在中國有著悠久的歷史。由于用具簡單，趣味性強，成為流行極為廣泛的棋藝活動。本文將利用Java實現這一經典游戲，需要的可以參考一下2022-02-02
這篇文章主要介紹了Java中的日期時間處理及格式化處理方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要為大家介紹了JSON Web Token(JWT)原理入門教程詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2022-04-04
tio-boot?jfinal-plugins框架整合redis示例詳解
這篇文章主要為大家介紹了tio-boot?jfinal-plugins框架整合redis示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
這篇文章主要介紹了詳解ElasticSearch6.4.0集群搭建，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-09-09
spring boot使用自定義配置的線程池執(zhí)行Async異步任務
這篇文章主要介紹了spring boot使用自定義配置的線程池執(zhí)行Async異步任務，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-01-01
這篇文章主要介紹了springmvc接口接收參數與請求參數格式的整理，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
在我們開發(fā)項目過程中,經常需要定時任務來幫助我們來做一些內容,本文介紹了springboot中設置定時任務的三種方法,主要包括@Scheduled注解,Quartz框架和xxl-job框架的實現,感興趣的可以了解一下2023-12-12
讀萬卷書不如行萬里路，只學書上的理論是遠遠不夠的，只有在實戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用java+SSM+JSP+maven+Mysql實現一個網上電子書城,大家可以在過程中查缺補漏，提升水平2022-01-01