Java 數據結構與算法系列精講之單向鏈表
概述
從今天開始, 小白我將帶大傢開啟 Jave 數據結構 & 算法的新篇章.
鏈表
鏈表 (Linked List) 是一種遞歸的動態數據結構. 鏈表以線性表的形式, 在每一個節點存放下一個節點的指針. 鏈表解決瞭數組需要先知道數據大小的缺點, 增加瞭節點的指針域, 空間開銷較大.
鏈表包括三類:
- 單向鏈表
- 雙向鏈表
- 循環鏈表
單向鏈表
單向鏈表 (Single Linked List) 是鏈表中最簡單的一種形式. 單向鏈表每個節點包含兩個部分, 第一部分是信息, 第二部分是下一個節點. (元素 + 指針)
單向鏈表實現
Node 類
// Node類
private class Node {
public E e; // 元素
private SingleLinkedList.Node next; // 下一個節點
// 構造
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前一個節點
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前一個節點
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前一個節點
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前一個節點
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;
// 遍歷所有節點
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
main
// main
public static void main(String[] args) {
// 創建單向鏈表
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; // 下一個節點
// 構造
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前一個節點
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前一個節點
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前一個節點
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前一個節點
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;
// 遍歷所有節點
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) {
// 創建單向鏈表
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 單向鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！