下面是Java链表(Linked List)基本原理与实现方法入门示例的完整攻略。
什么是链表
链表是一种线性的数据结构,由一系列节点组成。每个节点都包含了数据和指向下一个节点的指针。
相比于数组,链表的一个主要优点是在插入、删除元素时不需要移动其他元素,因为每个节点都有指向下一个节点的指针。但是,链表的缺点是不能像数组一样随机访问,只能从头部开始遍历。
实现方法
Java实现单向链表
Java实现单向链表需要定义一个Node类,用于表示链表中的节点。定义一个链表类LinkedList,拥有添加节点方法(addNode)、删除节点方法(deleteNode)、遍历节点方法(traverseNodes)、清空链表方法等方法。
例如,以下为Java实现单向链表的示例代码:
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public class LinkedList {
Node head;
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void deleteNode(int data) {
Node current = head;
Node previous = null;
while (current != null && current.data != data) {
previous = current;
current = current.next;
}
if (current != null) {
if (previous == null) {
head = current.next;
} else {
previous.next = current.next;
}
}
}
public void traverseNodes() {
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
public void clearList() {
head = null;
}
}
Java实现双向链表
Java实现双向链表需要在Node类中再添加前驱节点(previous)的指针,链表类中添加反向遍历节点方法(reverseTraverseNodes),其他方法和单向链表的实现类似。
例如,以下为Java实现双向链表的示例代码:
public class Node {
int data;
Node next;
Node previous;
public Node(int data) {
this.data = data;
}
}
public class DoublyLinkedList {
Node head;
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.previous = current;
}
}
public void deleteNode(int data) {
Node current = head;
while (current != null && current.data != data) {
current = current.next;
}
if (current != null) {
if (current.previous == null) {
head = current.next;
if (head != null) {
head.previous = null;
}
} else {
current.previous.next = current.next;
if (current.next != null) {
current.next.previous = current.previous;
}
}
}
}
public void traverseNodes() {
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
public void reverseTraverseNodes() {
Node current = head;
while (current.next != null) {
current = current.next;
}
while (current != null) {
System.out.println(current.data);
current = current.previous;
}
}
public void clearList() {
head = null;
}
}
示例说明
以下为使用单向链表实现LIFO(后进先出)栈的示例代码:
public class Stack {
LinkedList list;
public Stack() {
list = new LinkedList();
}
public void push(int data) {
list.addNode(data);
}
public int pop() {
Node current = list.head;
if (current == null) {
throw new NoSuchElementException();
} else if (current.next == null) {
list.head = null;
return current.data;
} else {
while (current.next.next != null) {
current = current.next;
}
int data = current.next.data;
current.next = null;
return data;
}
}
public void printStack() {
list.traverseNodes();
}
}
使用方式:
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3); // 栈中元素为 3 -> 2 -> 1
stack.pop(); // 弹出元素3,栈中元素为 2 -> 1
stack.push(4); // 栈中元素为 4 -> 2 -> 1
stack.printStack(); // 输出 4 2 1
以下为使用双向链表实现LIFO(后进先出)队列的示例代码:
public class Queue {
DoublyLinkedList list;
public Queue() {
list = new DoublyLinkedList();
}
public void enqueue(int data) {
list.addNode(data);
}
public int dequeue() {
Node current = list.head;
if (current == null) {
throw new NoSuchElementException();
} else if (current.next == null) {
list.head = null;
return current.data;
} else {
list.head = current.next;
current.next.previous = null;
return current.data;
}
}
public void printQueue() {
list.traverseNodes();
}
}
使用方式:
Queue queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3); // 队列中元素为 1 <- 2 <- 3
queue.dequeue(); // 弹出元素1,队列中元素为 2 <- 3
queue.enqueue(4); // 队列中元素为 2 <- 3 <- 4
queue.printQueue(); // 输出 2 3 4
以上两个示例代码对于链表的基本操作进行了展示,并且演示了如何通过链表实现栈和队列。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java链表(Linked List)基本原理与实现方法入门示例 - Python技术站