一、什麼是鏈表
鏈表是一種常用的線性數據結構，它由一系列結點（Node）組成。每個結點包含數據域和指針域，其中數據域存儲結點的數據信息，指針域存儲下一個結點的地址。鏈表中的結點可以在任何時間動態添加或刪除。
二、鏈表的分類
鏈表可以分為單向鏈表、雙向鏈表和循環鏈表三種類型。
- 單向鏈表: 每個結點只有一個指針域，指向下一結點。
- 雙向鏈表: 每個結點有兩個指針域，分別指向前驅結點和後繼結點。
- 循環鏈表: 單向循環鏈表和雙向循環鏈表是兩種形式的循環鏈表，它們的規則都是把鏈表的頭結點和尾結點相連從而形成一個環。
三、Java實現單向鏈表
下面的代碼展示了如何使用Java實現單向鏈表:
class Node {
// 數據域
private int data;
// 指針域
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
class LinkedList {
// 頭結點
private Node head;
// 鏈表長度
private int size;
public LinkedList() {
// 初始化頭結點，next指向null
head = new Node(0, null);
size = 0;
}
// 根據index獲取結點
private Node getNode(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = head.getNext();
for (int i = 0; i < index; i++) {
node = node.getNext();
}
return node;
}
// 插入結點
public void add(int index, int data) {
if (index size) {
throw new IndexOutOfBoundsException();
}
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.getNext();
}
Node node = new Node(data, prev.getNext());
prev.setNext(node);
size++;
}
// 刪除結點
public void remove(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.getNext();
}
Node node = prev.getNext();
prev.setNext(node.getNext());
size--;
}
// 修改結點
public void set(int index, int data) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
node.setData(data);
}
// 獲取鏈表長度
public int getSize() {
return size;
}
// 獲取結點數據
public int get(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
return node.getData();
}
}
上面的代碼中，LinkedList類包含了add、remove、set、getSize和get方法，分別實現了插入結點、刪除結點、修改結點、獲取鏈表長度和獲取結點數據的功能。同時，Node類表示鏈表的每個結點，包含數據域和指針域。
四、Java實現雙向鏈表
雙向鏈表由於結點有前驅結點和後繼結點兩個指針域，所以需要在Node類中添加前驅指針域prev。同時，在鏈表插入和刪除操作時還需要處理前驅結點的後繼指針。
下面的代碼展示了如何使用Java實現雙向鏈表:
class Node {
// 數據域
private int data;
// 前驅指針域
private Node prev;
// 後繼指針域
private Node next;
public Node(int data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
class DoublyLinkedList {
// 頭結點
private Node head;
// 尾結點
private Node tail;
// 鏈表長度
private int size;
public DoublyLinkedList() {
// 初始化頭結點和尾結點，prev和next分別指向null
head = new Node(0, null, null);
tail = new Node(0, head, null);
head.setNext(tail);
size = 0;
}
// 根據index獲取結點
private Node getNode(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node;
if (index < size / 2) {
// 從前往後遍歷
node = head.getNext();
for (int i = 0; i index; i--) {
node = node.getPrev();
}
}
return node;
}
// 插入結點
public void add(int index, int data) {
if (index size) {
throw new IndexOutOfBoundsException();
}
Node next = getNode(index);
Node prev = next.getPrev();
Node node = new Node(data, prev, next);
prev.setNext(node);
next.setPrev(node);
size++;
}
// 刪除結點
public void remove(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
Node prev = node.getPrev();
Node next = node.getNext();
prev.setNext(next);
next.setPrev(prev);
size--;
}
// 修改結點
public void set(int index, int data) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
node.setData(data);
}
// 獲取鏈表長度
public int getSize() {
return size;
}
// 獲取結點數據
public int get(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
return node.getData();
}
}
上面的代碼中，DoublyLinkedList類包含了add、remove、set、getSize和get方法，和LinkedList類相比需要多處理前驅指針和後繼指針的更新。同時，Node類表示鏈表的每個結點，包含數據域、前驅指針域和後繼指針域。
五、Java實現循環鏈表
循環鏈表在單向鏈表和雙向鏈表的基礎上，把鏈表的頭結點和尾結點相連從而形成一個環。在插入和刪除結點時，如果操作的位置是頭結點或尾結點則需要更新尾結點和頭結點的指針。
下面的代碼展示了如何使用Java實現單向循環鏈表:
class Node {
// 數據域
private int data;
// 指針域
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
class CircularLinkedList {
// 頭結點
private Node head;
// 鏈表長度
private int size;
public CircularLinkedList() {
// 初始化頭結點，next指向自身
head = new Node(0, null);
head.setNext(head);
size = 0;
}
// 根據index獲取結點
private Node getNode(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = head.getNext();
for (int i = 0; i < index; i++) {
node = node.getNext();
}
return node;
}
// 插入結點
public void add(int index, int data) {
if (index size) {
throw new IndexOutOfBoundsException();
}
if (index == size) {
// 插入尾結點
Node tail = head;
for (int i = 0; i < size; i++) {
tail = tail.getNext();
}
Node node = new Node(data, head);
tail.setNext(node);
} else {
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.getNext();
}
Node node = new Node(data, prev.getNext());
prev.setNext(node);
}
size++;
}
// 刪除結點
public void remove(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
if (index == size - 1) {
// 刪除尾結點
Node tail = head;
for (int i = 0; i < size; i++) {
tail = tail.getNext();
}
Node prev = getNode(index - 1);
prev.setNext(head);
tail = prev;
} else {
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.getNext();
}
Node node = prev.getNext();
prev.setNext(node.getNext());
}
size--;
}
// 修改結點
public void set(int index, int data) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
node.setData(data);
}
// 獲取鏈表長度
public int getSize() {
return size;
}
// 獲取結點數據
public int get(int index) {
if (index = size) {
throw new IndexOutOfBoundsException();
}
Node node = getNode(index);
return node.getData();
}
}
上面的代碼中，CircularLinkedList類包含了add、remove、set、getSize和get方法，和LinkedList類相比需要多處理尾結點的指針。同時，Node類表示鏈表的每個結點，包含數據域和指針
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/302730.html
微信掃一掃 
支付寶掃一掃 