双向链表数据结构
什么是双向链表？
双向链表是链表的一种变体，与单链表相比，它可以轻松地向前和向后导航。以下是理解双向链表概念的重要术语。
Link − 链表的每个链接都可以存储一个称为元素的数据。
Next − 链表的每个链接都包含一个指向下一个链接的链接，称为"Next"。
Prev − 链表的每个链接都包含一个指向上一个链接的链接，称为"Prev"。
链表 −链表包含指向第一个链接（称为 First）和最后一个链接（称为 Last）的连接链接。
双向链表表示
根据上图，以下是需要考虑的要点。
双向链表包含一个名为 first 和 last 的链接元素。
每个链接都包含一个数据字段和一个称为 next 的链接字段。
每个链接都通过其下一个链接与其下一个链接链接。
每个链接都通过其上一个链接与其上一个链接链接。
最后一个链接包含一个链接，如下所示null 标记列表末尾。
双向链表的基本操作
以下是列表支持的基本操作。
插入 − 在列表开头添加一个元素。
插入最后一个 − 在列表末尾添加一个元素。
插入后 − 在列表的某个元素后添加一个元素。
删除 − 删除列表开头的一个元素。
删除最后一个 −从列表末尾删除一个元素。
删除 − 使用键从列表中删除一个元素。
向前显示 − 以正向方式显示完整列表。
向后显示 − 以反向方式显示完整列表。
双向链表 - 在开头插入
在此操作中，我们创建一个包含三个隔间的新节点，一个包含数据，其他两个包含列表中前一个节点和后一个节点的地址。此新节点将插入到列表的开头。
算法
1. 开始 2. 创建一个包含三个变量的新节点：prev、data、next。 3. 将新数据存储到 data 变量中 4. 如果列表为空，则将新节点设为头节点。 5. 否则，将现有首节点的地址链接到 新节点的 next 变量，并将 prev 变量赋值为 null。 6. 将头节点指向新节点。 7. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//显示双向链表
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("
双向链表： ");
printList();
}
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//显示双向链表
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("双向链表： ");
printList();
return 0;
}
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
//双向链表的Java代码
import java.util.*;
class Node {
public int data;
public int key;
public Node next;
public Node prev;
public Node(int data, int key) {
this.data = data;
this.key = key;
this.next = null;
this.prev = null;
}
}
public class Main {
//此链接始终指向第一个链接
static Node head = null;
//此链接始终指向最后一个链接
static Node last = null;
static Node current = null;
// 列表为空
public static boolean is_empty() {
return head == null;
}
//显示双向链表
public static void print_list() {
Node ptr = head;
while (ptr != null) {
System.out.println("(" + ptr.key + "," + ptr.data + ")");
ptr = ptr.next;
}
}
//在第一个位置插入链接
public static void insert_first(int key, int data) {
//创建链接
Node link = new Node(data, key);
if (is_empty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head.prev = link;
}
//将其指向旧的第一个链接
link.next = head;
//首先指向新的第一个链接
head = link;
}
public static void main(String[] args) {
insert_first(1, 10);
insert_first(2, 20);
insert_first(3, 30);
insert_first(4, 1);
insert_first(5, 40);
insert_first(6, 56);
System.out.println("双向链表： ");
print_list();
}
}
输出
双向链表： (6,56)(5,40)(4,1)(3,30)(2,20)(1,10)
#双向链表的Python代码
class Node:
def __init__(self, data=None, key=None):
self.data = data
self.key = key
self.next = None
self.prev = None
#此链接始终指向第一个链接
head = None
#此链接始终指向最后一个链接
last = None
current = None
#列表为空
def is_empty():
return head == None
#显示双向链表
def print_list():
ptr = head
while ptr != None:
print(f"({ptr.key},{ptr.data})")
ptr = ptr.next
#在第一个位置插入链接
def insert_first(key, data):
global head, last
#创建链接
link = Node(data, key)
if is_empty():
#使其成为最后一个链接
last = link
else:
#更新第一个上一个链接
head.prev = link
#将其指向旧的第一个链接
link.next = head
#首先指向新的第一个链接
head = link
insert_first(1,10)
insert_first(2,20)
insert_first(3,30)
insert_first(4,1)
insert_first(5,40)
insert_first(6,56)
print("双向链表： ")
print_list()
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
双向链表 - 尾部插入
在此插入操作中，如果链表非空，则将新的输入节点添加到双向链表的尾部。如果链表为空，则将头节点指向新节点。
算法
1. 开始 2. 如果链表为空，则将节点添加到链表并将头节点指向该节点。 3. 如果链表非空，则找到链表的最后一个节点。 4. 在链表的最后一个节点和新节点之间创建链接。 5. 新节点将指向 NULL，因为它是新的最后一个节点。 6. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//显示双向链表
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
//在最后位置插入链接
void insertLast(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//使链接成为新的最后一个链接
last->next = link;
//将旧的最后一个节点标记为新链接的上一个
link->prev = last;
}
//指向最后一个新的最后一个节点
last = link;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertLast(5,40);
insertLast(6,56);
printf("双向链表： ");
printList();
}
输出
双向链表： (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//显示双向链表
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
//在最后位置插入链接
void insertLast(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//使链接成为新的最后一个链接
last->next = link;
//将旧的最后一个节点标记为新链接的上一个
link->prev = last;
}
//指向最后一个新的最后一个节点
last = link;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertLast(5,40);
insertLast(6,56);
printf("双向链表： ");
printList();
return 0;
}
输出
双向链表： (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)
import java.util.*;
class Node {
public int data;
public int key;
public Node next;
public Node prev;
public Node(int data, int key) {
this.data = data;
this.key = key;
this.next = null;
this.prev = null;
}
}
public class Main {
static Node head = null;
static Node last = null;
static Node current = null;
public static boolean isEmpty() {
return head == null;
}
public static void printList() {
Node ptr = head;
while (ptr != null) {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
}
}
public static void insertFirst(int key, int data) {
Node link = new Node(data, key);
if (isEmpty()) {
last = link;
} else {
head.prev = link;
}
link.next = head;
head = link;
}
public static void insertLast(int key, int data) {
Node link = new Node(data, key);
if (isEmpty()) {
last = link;
} else {
last.next = link;
link.prev = last;
}
last = link;
}
public static void main(String[] args) {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertLast(5,40);
insertLast(6,56);
System.out.print("双向链表： ");
printList();
}
}
输出
双向链表： (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)
class Node:
def __init__(self, data=None, key=None):
self.data = data
self.key = key
self.next = None
self.prev = None
head = None
last = None
current = None
def isEmpty():
return head == None
def printList():
ptr = head
while ptr != None:
print(f"({ptr.key},{ptr.data})", end=" ")
ptr = ptr.next
def insertFirst(key, data):
global head, last
link = Node(data, key)
if isEmpty():
last = link
else:
head.prev = link
link.next = head
head = link
def insertLast(key, data):
global head, last
link = Node(data, key)
if isEmpty():
last = link
else:
last.next = link
link.prev = last
last = link
insertFirst(1,10)
insertFirst(2,20)
insertFirst(3,30)
insertFirst(4,1)
insertLast(5,40)
insertLast(6,56)
print("双向链表： ", end="")
printList()
输出
双向链表： (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)
双向链表 - 从头删除
此删除操作会删除双向链表中现有的第一个节点。链表头会移至下一个节点，并且链接会被移除。
算法
1. 开始 2. 检查双向链表的状态 3. 如果链表为空，则无法删除 4. 如果链表不为空，则链表头指针会 移至下一个节点。 5. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//显示双向链表
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
//删除第一项
struct node* deleteFirst(){
//保存对第一个链接的引用
struct node *tempLink = head;
//如果只有一个链接
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//返回已删除的链接
return tempLink;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("双向链表：
");
printList();
printf("
删除第一条记录后的列表：
");
deleteFirst();
printList();
}
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 删除第一条记录后的列表：(5,40) (4,1) (3,30) (2,20) (1,10)
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//显示双向链表
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
//删除第一项
struct node* deleteFirst(){
//保存对第一个链接的引用
struct node *tempLink = head;
//如果只有一个链接
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//返回已删除的链接
return tempLink;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("双向链表：
");
printList();
printf("
删除第一条记录后的列表：
");
deleteFirst();
printList();
return 0;
}
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 删除第一条记录后的列表： (5,40) (4,1) (3,30) (2,20) (1,10)
//双向链表的Java代码
import java.util.*;
class Node {
public int data;
public int key;
public Node next;
public Node prev;
public Node(int data, int key) {
this.data = data;
this.key = key;
this.next = null;
this.prev = null;
}
}
public class Main {
//此链接始终指向第一个链接
public static Node head = null;
//此链接始终指向最后一个链接
public static Node last = null;
//this link always point to current Link
public static Node current = null;
//列表为空
public static boolean isEmpty() {
return head == null;
}
//显示双向链表
public static void printList() {
Node ptr = head;
while (ptr != null) {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
}
}
//在第一个位置插入链接
public static void insertFirst(int key, int data) {
//创建链接
Node link = new Node(data, key);
if (isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head.prev = link;
}
//将其指向旧的第一个链接
link.next = head;
head = link;
}
//delete the first item
public static Node deleteFirst() {
//保存对第一个链接的引用
Node tempLink = head;
//如果只有一个链接
if (head.next == null) {
last = null;
} else {
head.next.prev = null;
}
head = head.next;
//返回已删除的链接
return tempLink;
}
public static void main(String[] args) {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);
System.out.print("双向链表：
");
printList();
System.out.print("
删除第一条记录后的列表：
");
deleteFirst();
printList();
}
}
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 删除第一条记录后的列表： (5,40) (4,1) (3,30) (2,20) (1,10)
#Python code for doubly linked list
class Node:
def __init__(self, data=None, key=None):
self.data = data
self.key = key
self.next = None
self.prev = None
#此链接始终指向第一个链接
head = None
#此链接始终指向最后一个链接
last = None
current = None
#列表为空
def isEmpty():
return head == None
#显示双向链表
def printList():
ptr = head
while ptr != None:
print(f"({ptr.key},{ptr.data}) ", end="")
ptr = ptr.next
#在第一个位置插入链接
def insertFirst(key, data):
#创建链接
global head, last
link = Node(data, key)
if isEmpty():
#使其成为最后一个链接
last = link
else:
#更新第一个上一个链接
head.prev = link
#将其指向旧的第一个链接
link.next = head
head = link
#delete first item
def deleteFirst():
#保存对第一个链接的引用
global head, last
tempLink = head
#if only one link
if head.next == None:
last = None
else:
head.next.prev = None
head = head.next
#返回已删除的链接
return tempLink
insertFirst(1,10)
insertFirst(2,20)
insertFirst(3,30)
insertFirst(4,1)
insertFirst(5,40)
insertFirst(6,56)
print("双向链表：")
printList()
print("
List after deleting first record:")
deleteFirst()
printList()
输出
双向链表： (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 删除第一条记录后的列表： (5,40) (4,1) (3,30) (2,20) (1,10)
双向链表 - 完整实现
以下是各种编程语言中双向链表的完整实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//按从头到尾的顺序显示列表
void displayForward(){
//从头开始
struct node *ptr = head;
//导航至列表末尾
printf("
[ ");
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//从最后一个元素到第一个元素显示列表
void displayBackward(){
//从最后一个元素开始
struct node *ptr = last;
//导航到列表开头
printf("
[ ");
while(ptr != NULL) {
//打印数据
printf("(%d,%d) ",ptr->key,ptr->data);
//移动到下一个项目
ptr = ptr ->prev;
printf(" ");
}
printf(" ]");
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
//在最后位置插入链接
void insertLast(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//使链接成为新的最后一个链接
last->next = link;
//将旧的最后一个节点标记为新链接的上一个
link->prev = last;
}
//指向最后一个新的最后一个节点
last = link;
}
//删除第一项
struct node* deleteFirst(){
//保存对第一个链接的引用
struct node *tempLink = head;
//如果只有一个链接
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//返回已删除的链接
return tempLink;
}
//删除最后一个位置的链接
struct node* deleteLast(){
//保存对最后一个链接的引用
struct node *tempLink = last;
//如果只有一个链接
if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//返回已删除的链接
return tempLink;
}
//删除具有给定键的链接
struct node* delete(int key){
//从第一个链接开始
struct node* current = head;
struct node* previous = NULL;
//如果列表为空
if(head == NULL) {
return NULL;
}
//浏览列表
while(current->key != key) {
//如果它是最后一个节点
if(current->next == NULL) {
return NULL;
} else {
//存储对当前链接的引用
previous = current;
//移至下一个链接
current = current->next;
}
}
//找到匹配项，更新链接
if(current == head) {
//更改第一个链接以指向下一个链接
head = head->next;
} else {
//绕过当前链接
current->prev->next = current->next;
}
if(current == last) {
//将最后一个链接更改为指向上一个链接
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data){
//从第一个链接开始
struct node *current = head;
//如果列表为空
if(head == NULL) {
return false;
}
//浏览列表
while(current->key != key) {
//如果它是最后一个节点
if(current->next == NULL) {
return false;
} else {
//移至下一个链接
current = current->next;
}
}
//创建链接
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = key;
newLink->data = 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;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("
List (First to Last): ");
displayForward();
printf("
");
printf("
List (Last to first): ");
displayBackward();
printf("
List , after deleting first record: ");
deleteFirst();
displayForward();
printf("
List , after deleting last record: ");
deleteLast();
displayForward();
printf("
List , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();
printf("
List , after delete key(4) : ");
delete(4);
displayForward();
}
输出
List (First to Last): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ] List (Last to first): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ] List , after deleting first record: [ (5,40) (4,1) (3,30) (2,20) (1,10) ] List , after deleting last record: [ (5,40) (4,1) (3,30) (2,20) ] List , insert after key(4) : [ (5,40) (4,1) (4,13) (3,30) (2,20) ] List , after delete key(4) : [ (5,40) (4,13) (3,30) (2,20) ]
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
using namespace std;
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//此链接始终指向第一个链接
struct node *head = NULL;
//此链接始终指向最后一个链接
struct node *last = NULL;
struct node *current = NULL;
//列表为空
bool isEmpty(){
return head == NULL;
}
//按从头到尾的顺序显示列表
void displayForward(){
//从头开始
struct node *ptr = head;
//导航至列表末尾
cout << "
[ ";
while(ptr != NULL) {
cout << "(" << ptr->key << "," << ptr->data << ")";
ptr = ptr->next;
}
cout << " ]" << endl;
}
//从最后到第一显示列表
void displayBackward(){
//从最后一个开始
struct node *ptr = last;
//导航至列表开头
cout << "
[ ";
while(ptr != NULL) {
//打印数据
cout << "(" << ptr->key << "," << ptr->data << ")";
//移动到下一个项目
ptr = ptr ->prev;
cout << " ";
}
cout << " ]" << endl;
}
//在第一个位置插入链接
void insertFirst(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//更新第一个上一个链接
head->prev = link;
}
//将其指向旧的第一个链接
link->next = head;
//首先指向新的第一个链接
head = link;
}
//在最后位置插入链接
void insertLast(int key, int data){
//创建链接
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//使其成为最后一个链接
last = link;
} else {
//使链接成为新的最后一个链接
last->next = link;
//将旧的最后一个节点标记为新链接的上一个
link->prev = last;
}
//指向最后一个新的最后一个节点
last = link;
}
//删除第一项
struct node* deleteFirst(){
//保存对第一个链接的引用
struct node *tempLink = head;
//如果只有一个链接
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//返回已删除的链接
return tempLink;
}
//删除最后一个位置的链接
struct node* deleteLast(){
//保存对最后一个链接的引用
struct node *tempLink = last;
//如果只有一个链接
if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//返回已删除的链接
return tempLink;
}
//删除具有给定键的链接
struct node* deletenode(int key){
//从第一个链接开始
struct node* current = head;
struct node* previous = NULL;
//如果列表为空
if(head == NULL) {
return NULL;
}
//浏览列表
while(current->key != key) {
//如果它是最后一个节点
if(current->next == NULL) {
return NULL;
} else {
//存储对当前链接的引用
previous = current;
//移至下一个链接
current = current->next;
}
}
//找到匹配项，更新链接
if(current == head) {
//更改第一个链接以指向下一个链接
head = head->next;
} else {
//绕过当前链接
current->prev->next = current->next;
}
if(current == last) {
//将最后一个链接更改为指向上一个链接
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data){
//从第一个链接开始
struct node *current = head;
//如果列表为空
if(head == NULL) {
return false;
}
//浏览列表
while(current->key != key) {
//如果它是最后一个节点
if(current->next == NULL) {
return false;
} else {
//移至下一个链接
current = current->next;
}
}
//创建链接
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = key;
newLink->data = 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;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("
List (First to Last): ");
displayForward();
printf("
");
printf("
List (Last to first): ");
displayBackward();
printf("
List , after deleting first record: ");
deleteFirst();
displayForward();
printf("
List , after deleting last record: ");
deleteLast();
displayForward();
printf("
List , insert after key(4) : ");
insertAfter(4, 7, 13);
displayForward();
printf("
List , after delete key(4) : ");
deletenode(4);
displayForward();
return 0;
}
输出
List (First to Last): [ (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ] List (Last to First): [ (1, 10) (2, 20) (3, 30) (4, 1) (5, 40) (6, 56) ] List, after deleting first record: [ (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ] List, after deleting last record: [ (5, 40) (4, 1) (3, 30) (2, 20) ] List, insert after key(4): [ (5, 40) (4, 1) (7, 13) (3, 30) (2, 20) ] List, after delete key(4): [ (5, 40) (7, 13) (3, 30) (2, 20) ]
class Node {
int data;
int key;
Node next;
Node prev;
public Node(int key, int data) {
this.key = key;
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
Node head;
Node last;
boolean isEmpty() {
return head == null;
}
void displayForward() {
Node ptr = head;
System.out.print("[ ");
while (ptr != null) {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
}
System.out.println("]");
}
void displayBackward() {
Node ptr = last;
System.out.print("[ ");
while (ptr != null) {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.prev;
}
System.out.println("]");
}
void insertFirst(int key, int data) {
Node link = new Node(key, data);
if (isEmpty()) {
last = link;
} else {
head.prev = link;
}
link.next = head;
head = link;
}
void insertLast(int key, int data) {
Node link = new Node(key, data);
if (isEmpty()) {
last = link;
} else {
last.next = link;
link.prev = last;
}
last = link;
}
Node deleteFirst() {
if (isEmpty()) {
return null;
}
Node tempLink = head;
if (head.next == null) {
last = null;
} else {
head.next.prev = null;
}
head = head.next;
return tempLink;
}
Node deleteLast() {
if (isEmpty()) {
return null;
}
Node tempLink = last;
if (head.next == null) {
head = null;
} else {
last.prev.next = null;
}
last = last.prev;
return tempLink;
}
Node delete(int key) {
Node current = head;
Node previous = null;
if (head == null) {
return null;
}
while (current.key != key) {
if (current.next == null) {
return null;
} else {
previous = current;
current = current.next;
}
}
if (current == head) {
head = head.next;
} else {
current.prev.next = current.next;
}
if (current == last) {
last = current.prev;
} else {
current.next.prev = current.prev;
}
return current;
}
boolean insertAfter(int key, int newKey, int data) {
Node current = head;
if (head == null) {
return false;
}
while (current.key != key) {
if (current.next == null) {
return false;
} else {
current = current.next;
}
}
Node newLink = new Node(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;
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertFirst(1, 10);
dll.insertFirst(2, 20);
dll.insertFirst(3, 30);
dll.insertFirst(4, 1);
dll.insertFirst(5, 40);
dll.insertFirst(6, 56);
System.out.println("List (First to Last):");
dll.displayForward();
System.out.println();
System.out.println("List (Last to First):");
dll.displayBackward();
System.out.println("List, after deleting first record:");
dll.deleteFirst();
dll.displayForward();
System.out.println("List, after deleting last record:");
dll.deleteLast();
dll.displayForward();
System.out.println("List, insert after key(4):");
dll.insertAfter(4, 7, 13);
dll.displayForward();
System.out.println("List, after delete key(4):");
dll.delete(4);
dll.displayForward();
}
}
输出
List (First to Last): [ (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ] List (Last to First): [ (1, 10) (2, 20) (3, 30) (4, 1) (5, 40) (6, 56) ] List, after deleting first record: [ (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ] List, after deleting last record: [ (5, 40) (4, 1) (3, 30) (2, 20) ] List, insert after key(4): [ (5, 40) (4, 1) (7, 13) (3, 30) (2, 20) ] List, after delete key(4): [ (5, 40) (7, 13) (3, 30) (2, 20) ]
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.last = None
def is_empty(self):
return self.head is None
def display_forward(self):
ptr = self.head
print("[", end=" ")
while ptr:
print("({}, {})".format(ptr.key, ptr.data), end=" ")
ptr = ptr.next
print("]")
def display_backward(self):
ptr = self.last
print("[", end=" ")
while ptr:
print("({}, {})".format(ptr.key, ptr.data), end=" ")
ptr = ptr.prev
print("]")
def insert_first(self, key, data):
link = Node(key, data)
if self.is_empty():
self.last = link
else:
self.head.prev = link
link.next = self.head
self.head = link
def insert_last(self, key, data):
link = Node(key, data)
if self.is_empty():
self.last = link
else:
self.last.next = link
link.prev = self.last
self.last = link
def delete_first(self):
if self.is_empty():
return None
temp_link = self.head
if self.head.next is None:
self.last = None
else:
self.head.next.prev = None
self.head = self.head.next
return temp_link
def delete_last(self):
if self.is_empty():
return None
temp_link = self.last
if self.head.next is None:
self.head = None
else:
self.last.prev.next = None
self.last = self.last.prev
return temp_link
def delete(self, key):
current = self.head
while current and current.key != key:
current = current.next
if current is None:
return None
if current == self.head:
self.head = self.head.next
else:
current.prev.next = current.next
if current == self.last:
self.last = current.prev
else:
current.next.prev = current.prev
return current
def insert_after(self, key, new_key, data):
current = self.head
while current and current.key != key:
current = current.next
if current is None:
return False
new_link = Node(new_key, data)
if current == self.last:
new_link.next = None
self.last = new_link
else:
new_link.next = current.next
current.next.prev = new_link
new_link.prev = current
current.next = new_link
return True
# Example usage
dll = DoublyLinkedList()
dll.insert_first(1, 10)
dll.insert_first(2, 20)
dll.insert_first(3, 30)
dll.insert_first(4, 1)
dll.insert_first(5, 40)
dll.insert_first(6, 56)
print("List (First to Last):")
dll.display_forward()
print()
print("List (Last to First):")
dll.display_backward()
print("List, after deleting first record:")
dll.delete_first()
dll.display_forward()
print("List, after deleting last record:")
dll.delete_last()
dll.display_forward()
print("List, insert after key(4):")
dll.insert_after(4, 7, 13)
dll.display_forward()
print("List, after delete key(4):")
dll.delete(4)
dll.display_forward()
输出
List (First to Last): [ (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ] List (Last to First): [ (1, 10) (2, 20) (3, 30) (4, 1) (5, 40) (6, 56) ] List, after deleting first record: [ (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ] List, after deleting last record: [ (5, 40) (4, 1) (3, 30) (2, 20) ] List, insert after key(4): [ (5, 40) (4, 1) (7, 13) (3, 30) (2, 20) ] List, after delete key(4): [ (5, 40) (7, 13) (3, 30) (2, 20) ]
