双向链表（双向链表java实现）

双向链表是一种链式数据结构，它可以在节点中同时保存前一个和后一个节点的引用。这种数据结构允许双向遍历，并且可以在 O(1) 时间复杂度下进行删除、添加和修改操作。

一级标题：双向链表的定义和特点

双向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据和两个指针。这两个指针分别指向前一个和后一个节点，因此双向链表也被称为双向列表。与单向链表不同的是，双向链表可以双向遍历，可以在任意位置进行删除、添加和修改操作。

二级标题：双向链表的节点结构和指针定义

在双向链表中，每个节点通常包含三个部分：前驱指针 prev，后继指针 next 和数据域 data。其中，prev 指向前驱节点的地址，next 指向后继节点的地址，data 存储该节点的数据。

```

struct Node

int data;

Node* prev;

Node* next;

};

```

三级标题：双向链表的操作

1. 添加操作

向双向链表中添加一个新节点，需要考虑两种情况：插入到链表头和插入到链表尾。

- 在链表头插入节点

在链表头插入一个新节点时，需要将新节点的 next 指向原来的头节点，将原来的头节点的 prev 指向新节点，并将链表头指针指向新节点的地址。

```

void insertAtHead(Node** head, int data)

Node* newNode = new Node();

newNode->data = data;

newNode->prev = nullptr;

newNode->next = *head;

if (*head != nullptr)

(*head)->prev = newNode;

*head = newNode;

```

- 在链表尾插入节点

在链表尾插入一个新节点时，需要将新节点的 prev 指向原来的尾节点，将原来的尾节点的 next 指向新节点，并将链表尾指针指向新节点的地址。

```

void insertAtTail(Node** tail, int data)

Node* newNode = new Node();

newNode->data = data;

newNode->prev = *tail;

newNode->next = nullptr;

if (*tail != nullptr)

(*tail)->next = newNode;

*tail = newNode;

```

2. 删除操作

删除双向链表中的节点时，需要考虑节点的位置：在链表头、链表尾和链表中间。

- 删除链表头节点

```

void deleteAtHead(Node** head)

if (*head == nullptr)

return;

Node* temp = *head;

*head = (*head)->next;

if (*head != nullptr)

(*head)->prev = nullptr;

delete temp;

```

- 删除链表尾节点

```

void deleteAtTail(Node** tail)

if (*tail == nullptr)

return;

Node* temp = *tail;

*tail = (*tail)->prev;

if (*tail != nullptr)

(*tail)->next = nullptr;

delete temp;

```

- 删除链表中的节点

```

void deleteNode(Node** head, Node** tail, int data)

if (*head == nullptr)

return;

if ((*head)->data == data)

{

deleteAtHead(head);

return;

}

if ((*tail)->data == data)

{

deleteAtTail(tail);

return;

}

Node* current = (*head)->next;

while (current != nullptr && current->data != data)

current = current->next;

if (current == nullptr)

return;

current->prev->next = current->next;

current->next->prev = current->prev;

delete current;

```

3. 遍历操作

双向链表可以从头节点或尾节点开始遍历，也可以反向遍历。

```

void printList(Node* head)

while (head != nullptr)

{

cout << head->data << " ";

head = head->next;

}

cout << endl;

void printListReverse(Node* tail)

while (tail != nullptr)

{

cout << tail->data << " ";

tail = tail->prev;

}

cout << endl;

```

四级标题：双向链表的优缺点

双向链表的主要优点是可以在任意位置 O(1) 时间内进行插入和删除操作，同时可以双向遍历链表。然而，与单向链表相比，双向链表需要额外的空间来存储指向前驱节点的指针，因此占用的内存空间更大。

五级标题：总结

双向链表是一种常用的链式数据结构，相对于单向链表具有更强的灵活性和更快的操作速度。在实际开发中，我们应根据实际情况选择不同的数据结构，以满足不同的需求。