- 数据结构与算法
- DSA - 主页
- DSA - 概述
- DSA - 环境设置
- 数据结构
- DSA - 数据结构基础知识
- DSA - 数据结构和类型
- DSA - 数组数据结构
- 链表
- DSA - 链表基础知识
- DSA - 双向链表
- DSA - 循环链表
- 堆栈和队列
- DSA - 堆栈
- DSA - 表达式解析
- DSA-队列
- 图数据结构
- DSA - 图数据结构
- DSA-深度优先遍历
- DSA-广度优先遍历
- DSA——生成树
- 树数据结构
- DSA - 树数据结构
- DSA - 树遍历
- DSA - 二叉搜索树
- DSA - AVL 树
- DSA - 红黑树
- DSA - B 树
- DSA - B+ 树
- DSA - 八字树
- DSA - 尝试
- DSA-堆
- 递归
- DSA - 递归基础知识
- DSA - 河内塔
- DSA - 斐波那契数列
- DSA 有用资源
- DSA - 问题与解答
- DSA - 快速指南
- DSA - 有用的资源
- DSA - 讨论
数据结构双向链表
双链表是链表的一种变体，与单链表相比，双链表可以以两种方式轻松向前和向后导航。以下是理解双向链表概念的重要术语。
链接- 链表的每个链接都可以存储称为元素的数据。
Next - 链表的每个链接都包含一个指向下一个链接（称为 Next）的链接。
Prev - 链表的每个链接都包含指向上一个称为 Prev 的链接的链接。
链接列表- 链接列表包含指向名为 First 的第一个链接和名为 Last 的最后一个链接的连接链接。
双向链表表示
根据上图，以下是需要考虑的要点。
双向链表包含一个称为第一个和最后一个的链接元素。
每个链接都带有一个数据字段和一个称为 next 的链接字段。
每个链接都使用其下一个链接与其下一个链接链接。
每个链接都使用其先前的链接与其先前的链接链接。
最后一个链接带有一个空链接来标记列表的结尾。
基本操作
以下是列表支持的基本操作。
插入- 在列表的开头添加一个元素。
删除- 删除列表开头的元素。
Insert Last - 在列表末尾添加一个元素。
删除最后一个- 从列表末尾删除一个元素。
Insert After - 在列表的项目之后添加一个元素。
删除- 使用键从列表中删除元素。
显示向前- 以向前的方式显示完整列表。
向后显示- 以向后的方式显示完整列表。
在开头插入
在此操作中，我们创建一个具有三个部分的新节点，一个包含数据，其他包含列表中前一个和下一个节点的地址。这个新节点被插入到列表的开头。
算法
1. START 2. Create a new node with three variables: prev, data, next. 3. Store the new data in the data variable 4. If the list is empty, make the new node as head. 5. Otherwise, link the address of the existing first node to the next variable of the new node, and assign null to the prev variable. 6. Point the head to the new node. 7. END
例子
以下是此操作在各种编程语言中的实现 -
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the doubly linked list
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nDoubly Linked List: ");
printList();
}
输出
Doubly Linked List: (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;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the doubly linked list
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nDoubly Linked List: ");
printList();
return 0;
}
输出
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
//Java code for doubly linked list
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 {
//this link always point to first Link
static Node head = null;
//this link always point to last Link
static Node last = null;
static Node current = null;
// is list empty
public static boolean is_empty() {
return head == null;
}
//display the doubly linked list
public static void print_list() {
Node ptr = head;
while (ptr != null) {
System.out.println("(" + ptr.key + "," + ptr.data + ")");
ptr = ptr.next;
}
}
//insert link at the first location
public static void insert_first(int key, int data) {
//create a link
Node link = new Node(data, key);
if (is_empty()) {
//make it the last link
last = link;
} else {
//update first prev link
head.prev = link;
}
//point it to old first link
link.next = head;
//point first to new first link
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("\nDoubly Linked List: ");
print_list();
}
}
输出
Doubly Linked List: (6,56)(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
#this link always point to first Link
head = None
#this link always point to last Link
last = None
current = None
#is list empty
def is_empty():
return head == None
#display the doubly linked list
def print_list():
ptr = head
while ptr != None:
print(f"({ptr.key},{ptr.data})")
ptr = ptr.next
#insert link at the first location
def insert_first(key, data):
global head, last
#create a link
link = Node(data, key)
if is_empty():
#make it the last link
last = link
else:
#update first prev link
head.prev = link
#point it to old first link
link.next = head
#point first to new first link
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("\nDoubly Linked List: ")
print_list()
输出
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
开头删除
该删除操作删除双向链表中现有的第一个节点。头被移动到下一个节点，并且链接被删除。
算法
1. START 2. Check the status of the doubly linked list 3. If the list is empty, deletion is not possible 4. If the list is not empty, the head pointer is shifted to the next node. 5. END
例子
以下是此操作在各种编程语言中的实现 -
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the doubly linked list
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nDoubly Linked List: ");
printList();
printf("\nList after deleting first record: ");
deleteFirst();
printList();
}
输出
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) List after deleting first record: (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;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the doubly linked list
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nDoubly Linked List: ");
printList();
printf("\nList after deleting first record: ");
deleteFirst();
printList();
return 0;
}
输出
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10)
//Java code for doubly linked list
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 {
//this link always point to first Link
public static Node head = null;
//this link always point to last Link
public static Node last = null;
//this link always point to current Link
public static Node current = null;
//is list empty
public static boolean isEmpty() {
return head == null;
}
//display the doubly linked list
public static void printList() {
Node ptr = head;
while (ptr != null) {
System.out.print("(" + ptr.key + "," + ptr.data + ") ");
ptr = ptr.next;
}
}
//insert link at the first location
public static void insertFirst(int key, int data) {
//create a link
Node link = new Node(data, key);
if (isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head.prev = link;
}
//point it to old first link
link.next = head;
head = link;
}
//delete the first item
public static Node deleteFirst() {
//save reference to first link
Node tempLink = head;
//if only one link
if (head.next == null) {
last = null;
} else {
head.next.prev = null;
}
head = head.next;
//return the deleted link
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("\nDoubly Linked List: ");
printList();
System.out.print("\nList after deleting first record: ");
deleteFirst();
printList();
}
}
输出
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) List after deleting first record: (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
#this link always point to first Link
head = None
#this link always point to last Link
last = None
current = None
#is list empty
def isEmpty():
return head == None
#display the doubly linked list
def printList():
ptr = head
while ptr != None:
print(f"({ptr.key},{ptr.data}) ", end="")
ptr = ptr.next
#insert link at the first location
def insertFirst(key, data):
#create a link
global head, last
link = Node(data, key)
if isEmpty():
#make it the last link
last = link
else:
#update first prev link
head.prev = link
#point it to old first link
link.next = head
head = link
#delete first item
def deleteFirst():
#save reference to first link
global head, last
tempLink = head
#if only one link
if head.next == None:
last = None
else:
head.next.prev = None
head = head.next
#return the deleted link
return tempLink
insertFirst(1,10)
insertFirst(2,20)
insertFirst(3,30)
insertFirst(4,1)
insertFirst(5,40)
insertFirst(6,56)
print("\nDoubly Linked List: ", end="")
printList()
print("\nList after deleting first record: ")
deleteFirst()
printList()
输出
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10)
在末尾插入
在这个插入操作中，新的输入节点被添加到双向链表的末尾；如果列表不为空。如果列表为空，则头将指向新节点。
算法
1. START 2. If the list is empty, add the node to the list and point the head to it. 3. If the list is not empty, find the last node of the list. 4. Create a link between the last node in the list and the new node. 5. The new node will point to NULL as it is the new last node. 6. END
例子
以下是此操作在各种编程语言中的实现 -
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the doubly linked list
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
void main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertLast(5,40);
insertLast(6,56);
printf("\nDoubly Linked List: ");
printList();
}
输出
Doubly Linked List: (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;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the doubly linked list
void printList(){
struct node *ptr = head;
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertLast(5,40);
insertLast(6,56);
printf("\nDoubly Linked List: ");
printList();
return 0;
}
输出
Doubly Linked List: (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("\nDoubly Linked List: ");
printList();
}
}
输出
Doubly Linked List: (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("\nDoubly Linked List: ", end="")
printList()
输出
Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)
完成实施
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the list in from first to last
void displayForward(){
//start from the beginning
struct node *ptr = head;
//navigate till the end of the list
printf("\n[ ");
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//display the list from last to first
void displayBackward(){
//start from the last
struct node *ptr = last;
//navigate till the start of the list
printf("\n[ ");
while(ptr != NULL) {
//print data
printf("(%d,%d) ",ptr->key,ptr->data);
//move to next item
ptr = ptr ->prev;
printf(" ");
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
//save reference to last link
struct node *tempLink = last;
//if only one link
if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//return the deleted link
return tempLink;
}
//delete a link with given key
struct node* delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL) {
return NULL;
}
//navigate through list
while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last) {
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data){
//start from the first link
struct node *current = head;
//if list is empty
if(head == NULL) {
return false;
}
//navigate through list
while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return false;
} else {
//move to next link
current = current->next;
}
}
//create a link
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("\nList (First to Last): ");
displayForward();
printf("\n");
printf("\nList (Last to first): ");
displayBackward();
printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();
printf("\nList , after deleting last record: ");
deleteLast();
displayForward();
printf("\nList , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();
printf("\nList , 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;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
//display the list in from first to last
void displayForward(){
//start from the beginning
struct node *ptr = head;
//navigate till the end of the list
cout << "\n[ ";
while(ptr != NULL) {
cout << "(" << ptr->key << "," << ptr->data << ")";
ptr = ptr->next;
}
cout << " ]" << endl;
}
//display the list from last to first
void displayBackward(){
//start from the last
struct node *ptr = last;
//navigate till the start of the list
cout << "\n[ ";
while(ptr != NULL) {
//print data
cout << "(" << ptr->key << "," << ptr->data << ")";
//move to next item
ptr = ptr ->prev;
cout << " ";
}
cout << " ]" << endl;
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
//save reference to last link
struct node *tempLink = last;
//if only one link
if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//return the deleted link
return tempLink;
}
//delete a link with given key
struct node* deletenode(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL) {
return NULL;
}
//navigate through list
while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last) {
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data){
//start from the first link
struct node *current = head;
//if list is empty
if(head == NULL) {
return false;
}
//navigate through list
while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return false;
} else {
//move to next link
current = current->next;
}
}
//create a link
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("\nList (First to Last): ");
displayForward();
printf("\n");
printf("\nList (Last to first): ");
displayBackward();
printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();
printf("\nList , after deleting last record: ");
deleteLast();
displayForward();
printf("\nList , insert after key(4) : ");
insertAfter(4, 7, 13);
displayForward();
printf("\nList , 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) ]