基于Java函数实现链表数据结构的方法详解
链表是一种常见的数据结构，可以用来存储和操作一系列元素。它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以有不同的实现方式，如单向链表、双向链表、循环链表等。在Java中，我们可以使用类来实现链表数据结构。
一、单向链表（SinglyLinkedList）
单向链表是最常见的链表实现方式。每个节点只有一个指向下一个节点的指针，最后一个节点的指针为null。基于Java函数实现单向链表数据结构需要定义一个Node类表示节点，并定义一个SinglyLinkedList类表示单向链表。Node类的代码如下：
public class Node {
public int value;
public Node next;
public Node (int value) {
this.value = value;
this.next = null;
}
}
其中，value变量表示节点的值，next变量表示指向下一个节点的指针。SinglyLinkedList类的代码如下：
public class SinglyLinkedList {
private Node head;
private int size;
public SinglyLinkedList() {
this.head = null;
this.size = 0;
}
public int size() {
return this.size;
}
public boolean isEmpty() {
return (this.head == null);
}
public void addFirst(int value) {
Node newNode = new Node(value);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
public void addLast(int value) {
Node newNode = new Node(value);
if (isEmpty()) {
this.head = newNode;
} else {
Node temp = this.head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
this.size++;
}
public void removeFirst() {
if (!isEmpty()) {
this.head = this.head.next;
this.size--;
}
}
public void removeLast() {
if (!isEmpty()) {
if (this.head.next == null) {
this.head = null;
} else {
Node temp = this.head;
while (temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
}
this.size--;
}
}
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
Node temp = this.head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp.value;
}
}
public void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
Node temp = this.head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
temp.value = value;
}
}
public void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
if (index == 0) {
addFirst(value);
} else if (index == size) {
addLast(value);
} else {
Node newNode = new Node(value);
Node temp = this.head;
for (int i = 0; i < index-1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
this.size++;
}
}
}
public void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
if (index == 0) {
removeFirst();
} else if (index == size-1) {
removeLast();
} else {
Node temp = this.head;
for (int i = 0; i < index-1; i++) {
temp = temp.next;
}
temp.next = temp.next.next;
this.size--;
}
}
}
}
SinglyLinkedList类包括以下方法：
- size()：返回链表中元素的个数。
- isEmpty()：判断链表是否为空。
- addFirst(int value)：在链表头部添加一个元素。
- addLast(int value)：在链表尾部添加一个元素。
- removeFirst()：删除链表头部的元素。
- removeLast()：删除链表尾部的元素。
- get(int index)：获取链表中第index个元素的值。
- set(int index, int value)：将链表中第index个元素的值设置为value。
- insert(int index, int value)：在链表中第index个位置插入一个元素。
- delete(int index)：删除链表中第index个元素。
二、双向链表（DoublyLinkedList）
双向链表是在单向链表的基础上增加了一个指向前一个节点的指针。双向链表可以从链表头和链表尾进行遍历，但是它需要占用更多的内存空间。基于Java函数实现双向链表数据结构需要定义一个DNode类表示节点，并定义一个DoublyLinkedList类表示双向链表。DNode类的代码如下：
public class DNode {
public int value;
public DNode prev;
public DNode next;
public DNode(int value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
其中，value变量表示节点的值，prev变量表示指向前一个节点的指针，next变量表示指向下一个节点的指针。DoublyLinkedList类的代码如下：
`
public class DoublyLinkedList {
private DNode head;
private DNode tail;
private int size;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public int size() {
return this.size;
}
public boolean isEmpty() {
return (this.head == null);
}
public void addFirst(int value) {
DNode newNode = new DNode(value);
if (isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
public void addLast(int value) {
DNode newNode = new DNode(value);
if (isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
public void removeFirst() {
if (!isEmpty()) {
if (size == 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
this.size--;
}
}
public void removeLast() {
if (!isEmpty()) {
if (size == 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
}
}
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
DNode temp = this.head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp.value;
}
}
public void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
DNode temp = this.head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
temp.value = value;
}
}
public void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of range!");
} else {
if (index == 0) {
addFirst(value);
} else if (index == size) {
addLast(value);
} else {
DNode newNode = new DNode(value);
DNode temp = this.head;
for (int i = 0; i < index-1; i++) {
temp = temp.next;
}
newNode.prev = temp;
newNode.next =