JAVA数据结构链表
Java数据结构链表
链表是一种常用的数据结构，由一系列节点组成，节点之间通过指针进行连接。每个节点由一个数据域和一个指针域组成，指针域指向下一个节点。
链表相比于数组有一些优势。链表的长度可以动态改变，不需要提前预留空间。插入和删除节点的时间复杂度为O(1)，数组需要移动后面的元素，时间复杂度为O(n)。在需要频繁插入和删除元素的情况下，链表更加适用。
在Java中，链表的实现方式有多种，比如单向链表、双向链表和循环链表等。下面以单向链表为例，介绍链表的实现过程。
我们需要定义一个节点类，包含数据域和指针域：
```
public class Node {
public int data;
public Node next;
}
```
我们定义一个链表类，包含头节点和一些基本操作：
```
public class LinkedList {
private Node head;
// 在链表末尾插入新节点
public void append(int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = null;
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// 在链表指定位置插入新节点
public void insert(int data, int position) {
Node newNode = new Node();
newNode.data = data;
newNode.next = null;
if (head == null) {
head = newNode;
} else if (position == 0) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
for (int i = 1; i < position; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
// 删除指定位置的节点
public void remove(int position) {
if (head == null) {
return;
}
if (position == 0) {
head = head.next;
} else {
Node current = head;
for (int i = 1; i < position; i++) {
current = current.next;
}
current.next = current.next.next;
}
}
// 输出链表中的所有节点
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
```
使用链表时可以按照以下步骤进行操作：
```
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.display(); // 输出1 2 3
linkedList.insert(4, 1);
linkedList.display(); // 输出1 4 2 3
linkedList.remove(2);
linkedList.display(); // 输出1 4 3
```
通过以上代码，我们可以实现基本的链表操作。链表还有其他操作，比如查找指定节点、反转链表等，可以根据实际需求进行扩展。
java数据结构之双向链表实现
Java数据结构之双向链表实现
链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据以及指向下一个节点和上一个节点的指针。双向链表是链表的一种特殊形式，每个节点都有一个指向前一个节点和后一个节点的指针。
在Java中，我们可以使用类来实现双向链表。我们需要定义一个节点类，包含数据和指针。
```java
class Node {
int data;
Node prev;
Node next;
}
```
在双向链表中，头节点是指向链表第一个元素的指针，尾节点是指向链表最后一个元素的指针。我们还需要一个变量来跟踪链表的大小。
```java
class DoublyLinkedList {
Node head;
Node tail;
int size;
}
```
我们可以实现双向链表的常见操作，如插入、删除和查找。
1. 插入操作
在双向链表中插入一个元素需要考虑两种情况：在链表头部插入和在链表中间或尾部插入。
如果链表为空，我们直接将新节点设置为头节点和尾节点。
```java
public void insertAtHead(int data) {
Node newNode = new Node();
newNode.data = data;
if (isEmpty()) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
```
如果链表不为空，我们可以在链表头部或链表中间插入新节点。
```java
public void insert(int data, int position) {
if (position < 0 || position > size) {
throw new IllegalArgumentException("Invalid position!");
}
if (position == 0) {
insertAtHead(data);
} else if (position == size) {
insertAtTail(data);
} else {
Node newNode = new Node();
newNode.data = data;
Node current = head;
for (int i = 0; i < position - 1; i++) {
current = current.next;
}
newNode.prev = current;
newNode.next = current.next;
current.next.prev = newNode;
current.next = newNode;
size++;
}
}
```
2. 删除操作
删除操作与插入操作类似，同样需要考虑头部和中间/尾部的情况。
```java
public void deleteAtHead() {
if (isEmpty()) {
throw new NoSuchElementException("Linked list is empty!");
}
head = head.next;
head.prev = null;
size--;
}
public void delete(int position) {
if (position < 0 || position >= size) {
throw new IllegalArgumentException("Invalid position!");
}
if (position == 0) {
deleteAtHead();
} else if (position == size - 1) {
deleteAtTail();
} else {
Node current = head;
for (int i = 0; i < position; i++) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
size--;
}
}
```
3. 查找操作
查找操作可以通过遍历链表来实现。
```java
public int get(int position) {
if (position < 0 || position >= size) {
throw new IllegalArgumentException("Invalid position!");
}
Node current = head;
for (int i = 0; i < position; i++) {
current = current.next;
}
return current.data;
}
```
以上是双向链表的基本实现，可以在需要频繁插入和删除元素的情况下提供更高的性能。在实际应用中，我们可以根据具体需求对双向链表进行扩展，添加其他操作或功能。