Data structure-4 双向链表 DoubleLinkedList--Java语言实现

1. 双向链表简介

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.

Link − Each link of a linked list can store a data called an element.

Next − Each link of a linked list contains a link to the next link
called Next.

Prev − Each link of a linked list contains a link to the previous link
called Prev.

LinkedList − A Linked List contains the connection link to the first
link called First and to the last link called Last.

双向链表是一种单链表的变体，双向链表可以双向遍历一个链表，维护一个head和tail节点实现，其实现细节和单链表相似度较高。

2. 双向链表demo

//DoubleList.java
package com.fqyuan.doublelinklist;
public class DoubleList<T> {
private Node head;
private Node tail;
private int num;
public DoubleList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public boolean isEmpty() {
return num == 0;
}
public int getNum() {
return num;
}
// Insert before the head node.
public boolean insertAtStart(T item) {
if (isEmpty()) {
head.value = item;
head.prev = null;
head.next = tail;
num++;
return true;
} else {
Node newNode = new Node();
newNode.value = item;
newNode.prev = null;
newNode.next = head;
head.prev = newNode;
head = newNode;
num++;
return true;
}
}
// Insert after the end node.
public boolean insertAtEnd(T item) {
if (isEmpty()) {
tail.value = item;
num++;
return true;
} else {
Node newNode = new Node();
newNode.value = item;
newNode.prev = tail.prev;
newNode.next = tail;
tail.prev.next = newNode;
tail.prev = newNode;
num++;
return true;
}
}
// Insert after a given position.
public boolean insertAtPos(int pos, T item) {
if (pos > num)
return false;
/*
* First find the position to insert. The position to insert will be 1
* to size.
*/
Node pNode = head;
for (int i = 0; i < pos - 1; i++) {
pNode = pNode.next;
}
Node qNode = pNode.next;
Node newNode = new Node();
newNode.value = item;
newNode.next = qNode;
newNode.prev = pNode;
// Attention, link the original node to the new.
pNode.next = newNode;
qNode.prev = newNode;
num++;
return true;
}
// Delete an item at a given position
public boolean deleteItem(int pos) {
if (pos > num)
return false;
if (isEmpty())
return false;
// First find the position to delete
if (pos == 1) {
Node pNode = head.next;
head.next = null;
head = pNode;
num--;
return true;
}
if (pos == num) {
Node tarNode = head;
for (int i = 0; i < pos - 1; i++) {
tarNode = tarNode.next;
}
tarNode.next = null;
num--;
return true;
}
Node tarNode = head;
for (int i = 0; i < pos - 1; i++) {
tarNode = tarNode.next;
}
Node preNode = tarNode.prev;
Node nextNode = tarNode.next;
preNode.next = nextNode;
nextNode.prev = preNode;
tarNode.next = null;
tarNode.prev = null;
return true;
}
// Select sort the list
public void selectSort() {
for (Node p = head; p.next != null; p = p.next) {
for (Node q = p.next; q != null; q = q.next) {
if ((int) p.value > (int) q.value) {
T temp = p.value;
p.value = q.value;
q.value = temp;
}
}
}
}
// Bubble sort the list
public void bubbleSort() {
for (Node p = head; p.next != null; p = p.next) {
for (Node q = head; q.next != null; q = q.next) {
if ((int) q.value > (int) q.next.value) {
T temp = q.value;
q.value = q.next.value;
q.next.value = temp;
}
}
}
}
public void printList() {
Node n = head;
while (n.next != null) {
System.out.print(n.value + " ");
n = n.next;
}
System.out.println();
}
public void printReverseList() {
Node n = tail.prev;
while (n != null) {
System.out.print(n.value + " ");
n = n.prev;
}
System.out.println();
}
class Node {
private T value;
private Node prev;
private Node next;
}
}
//DList.java
package com.fqyuan.doublelinklist;
import java.util.Random;
public class DList {
public static void main(String[] args) {
DoubleList<Integer> doubleList = new DoubleList<>();
Random random = new Random();
for (int i = 0; i < 10; i++) {
int val = random.nextInt(100);
doubleList.insertAtStart(val);
System.out.print(val + " ");
}
System.out.println();
System.out.println("The original oder is:");
doubleList.printList();
System.out.println("The reverse iteration is:");
doubleList.printReverseList();
System.out.println("Insert at start:");
doubleList.insertAtStart(111);
doubleList.printList();
System.out.println("Insert at end:");
doubleList.insertAtEnd(999);
doubleList.printList();
System.out.println("Insert at a given position: ");
doubleList.insertAtPos(5, 555);
doubleList.printList();
System.out.println("Delete a item at giben position: ");
doubleList.deleteItem(doubleList.getNum());
doubleList.printList();
// System.out.println("Bubble Sort the Double list:");
// doubleList.bubbleSort();
// doubleList.printList();
System.out.println("Select sort the Double list");
doubleList.selectSort();
doubleList.printList();
}
}
//Running result:
31 29 76 34 47 5 9 58 93 35
The original oder is:
35 93 58 9 5 47 34 76 29 31
The reverse iteration is:
31 29 76 34 47 5 9 58 93 35
Insert at start:
111 35 93 58 9 5 47 34 76 29 31
Insert at end:
111 35 93 58 9 5 47 34 76 29 31 999
Insert at a given position:
111 35 93 58 9 555 5 47 34 76 29 31 999
Delete a item at giben position:
111 35 93 58 9 555 5 47 34 76 29 31
Select sort the Double list
5 9 29 31 34 35 47 58 76 93 111 555

最后

以上就是顺心红牛为你收集整理的Data structure-4 双向链表 DoubleLinkedList--Java语言实现的全部内容，希望文章能够帮你解决Data structure-4 双向链表 DoubleLinkedList--Java语言实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。