使用 Java 的 DSA - 双向链表
双向链表基础知识
双向链表是链表的一种变体，与单链表相比，双向链表可以轻松地向前和向后导航。以下是理解双向链表概念的重要术语
链接 − 链表的每个链接都可以存储称为元素的数据。
下一个 − 链表的每个链接都包含一个指向下一个链接的链接，称为下一个。
上一个 − 链表的每个链接都包含一个指向上一个链接的链接，称为上一个。
链接列表 − LinkedList 包含指向第一个 Link(称为 First)和最后一个 Link(称为 Last)的连接链接。
双向链接列表表示
如上图所示，以下是需要考虑的重要点。
双向链接列表包含一个称为 first 和 last 的链接元素。
每个 Link 都带有一个数据字段和一个称为 next 的链接字段。
每个 Link 都使用其下一个链接与其下一个链接链接。
每个 Link 都使用其上一个链接与其上一个链接链接。
最后一个 Link 带有一个为 null 的 Link 来标记结束列表。
基本操作
以下是列表支持的基本操作。
插入 − 在列表开头添加一个元素。
删除 − 删除列表开头的一个元素。
插入最后一个 − 在列表末尾添加一个元素。
删除最后一个 − 从列表末尾删除一个元素。
在后面插入 − 在列表的某项后面添加一个元素。
删除 −使用键从列表中删除一个元素。
向前显示 − 以向前方式显示完整列表。
向后显示 − 以向后方式显示完整列表。
插入操作
以下代码演示了在双向链表开头的插入操作。
//在第一个位置插入链接
public void insertFirst(int key, int data){
//创建链接
Link link = new Link(key,data);
if(isEmpty()){
//使其成为最后一个链接
last = link;
}else {
//更新第一个上一个链接
first.prev = link;
}
//将其指向旧的第一个链接
link.next = first;
//将 first 指向新的第一个链接
first = link;
}
删除操作
以下代码演示了双向链表开头的删除操作。
//删除第一个位置的链接
public Link deleteFirst(){
//保存对第一个链接的引用
Link tempLink = first;
//如果只有一个链接
if(first.next == null){
last = null;
}else {
first.next.prev = null;
}
first = first.next;
//返回删除的链接
return tempLink;
}
在末尾插入操作
以下代码演示了在双向链表的最后一个位置插入操作。
//在最后一个位置插入链接
public void insertLast(int key, int data){
//创建链接
Link link = new Link(key,data);
if(isEmpty()){
//使其成为最后一个链接
last = link;
}else {
//使链接成为新的最后一个链接
last.next = link;
//将旧的最后一个节点标记为新链接的前一个
link.prev = last;
}
//将最后一个指向新的最后一个节点
last = link;
}
演示
Link.java
package com.tutorialspoint.list;
public class Link {
public int key;
public int data;
public Link next;
public Link prev;
public Link(int key, int data){
this.key = key;
this.data = data;
}
public void display(){
System.out.print("{"+key+","+data+"}");
}
}
DoublyLinkedList.java
package com.tutorialspoint.list;
public class DoublyLinkedList {
//此链接始终指向第一个链接
private Link first;
//此链接始终指向最后一个链接
private Link last;
// 创建一个空的链接列表
public DoublyLinkedList(){
first = null;
last = null;
}
//列表是否为空
public boolean isEmpty(){
return first == null;
}
//在第一个位置插入链接
public void insertFirst(int key, int data){
//创建链接
Link link = new Link(key,data);
if(isEmpty()){
//使其成为最后一个链接
last = link;
}else {
//更新第一个上一个链接
first.prev = link;
}
//将其指向旧的第一个链接
link.next = first;
//将 first 指向新的第一个链接
first = link;
}
//在最后位置插入链接
public void insertLast(int key, int data){
//创建链接
Link link = new Link(key,data);
if(isEmpty()){
//使其成为最后一个链接
last = link;
}else {
//使链接成为新的最后一个链接
last.next = link;
//将旧的最后一个节点标记为新链接的前一个
link.prev = last;
}
//将最后一个指向新的最后一个节点
last = link;
}
//删除第一个位置的链接
public Link deleteFirst(){
//保存对第一个链接的引用
Link tempLink = first;
//如果只有一个链接
if(first.next == null){
last = null;
}else {
first.next.prev = null;
}
first = first.next;
//返回删除的链接
return tempLink;
}
//删除最后一个位置的链接
public Link deleteLast(){
//保存对最后一个链接的引用
Link tempLink = last;
//如果只有一个链接
if(first.next == null){
first = null;
}else {
last.prev.next = null;
}
last = last.prev;
//返回删除的链接
return tempLink;
}
//从第一个到最后一个显示列表
public void displayForward(){
//从头开始
Link current = first;
//导航到列表末尾
System.out.print("[ ");
while(current != null){
//打印数据
current.display();
//移动到下一个项目
current = current.next;
System.out.print(" ");
}
System.out.print(" ]");
}
//从最后一个到第一个显示列表
public void displayBackward(){
//从最后一个开始
Link current = last;
//导航到列表开头
System.out.print("[ ");
while(current != null){
//打印数据
current.display();
//移动到下一个项目
current = current.prev;
System.out.print(" ");
}
System.out.print(" ]");
}
//删除指定键的链接
public Link delete(int key){
//从第一个链接开始
Link current = first;
//如果列表为空
if(first == null){
return null;
}
//浏览列表
while(current.key != key){
//如果它是最后一个节点
if(current.next == null){
return null;
}else{
//移动到下一个链接
current = current.next;
}
}
//找到匹配项，更新链接
if(current == first) {
//将 first 改为指向 next 链接
first = current.next;
}else {
//绕过当前链接
current.prev.next = current.next;
}
if(current == last){
//将最后一个链接改为指向上一个链接
last = current.prev;
}else {
current.next.prev = current.prev;
}
return current;
}
public boolean insertAfter(int key, int newKey, int data){
//从第一个链接开始
Link current = first;
//如果列表为空
if(first == null){
return false;
}
//浏览列表
while(current.key != key){
//如果它是最后一个节点
if(current.next == null){
return false;
}else{
//移动到下一个链接
current = current.next;
}
}
Link newLink = new Link(newKey,data);
if(current==last) {
newLink.next = null;
last = newLink;
}
else {
newLink.next = current.next;
current.next.prev = newLink;
}
newLink.prev = current;
current.next = newLink;
return true;
}
}
DoublyLinkedListDemo.java
package com.tutorialspoint.list;
public class DoublyLinkedListDemo {
public static void main(String args[]){
DoublyLinkedList list = new DoublyLinkedList();
list.insertFirst(1, 10);
list.insertFirst(2, 20);
list.insertFirst(3, 30);
list.insertLast(4, 1);
list.insertLast(5, 40);
list.insertLast(6, 56);
System.out.print("
List (First to Last): ");
list.displayForward();
System.out.println("");
System.out.print("
List (Last to first): ");
list.displayBackward();
System.out.print("
List , after deleting first record: ");
list.deleteFirst();
list.displayForward();
System.out.print("
List , after deleting last record: ");
list.deleteLast();
list.displayForward();
System.out.print("
List , insert after key(4) : ");
list.insertAfter(4,7, 13);
list.displayForward();
System.out.print("
List , after delete key(4) : ");
list.delete(4);
list.displayForward();
}
}
如果我们编译并运行上述程序，则会产生以下结果 −
List (First to Last): [ {3,30} {2,20} {1,10} {4,1} {5,40} {6,56} ]
List (Last to first): [ {6,56} {5,40} {4,1} {1,10} {2,20} {3,30} ]
List (First to Last) after deleting first record: [ {2,20} {1,10} {4,1} {5,40} {6,56} ]
List (First to Last) after deleting last record: [ {2,20} {1,10} {4,1} {5,40} ]
List (First to Last) insert after key(4) : [ {2,20} {1,10} {4,1} {7,13} {5,40} ]
List (First to Last) after delete key(4) : [ {2,20} {1,10} {7,13} {5,40} ]
