数据结构之双向链表

双向链表（双链表），每个结点包含两个指针，分别指向当前结点的直接前驱 prev 和直接后继 next。所以，可以从表中的任意结点出发，访问它的前驱结点和后继结点。头结点的前驱和尾结点的后继分别指向 NULL。

![Image]({{ site.baseurl }}/images/DLList.png)

与单链表的对比

与单链表对比:

能够方便地向前，向后遍历
提供相应的结点，插入删除时更有效
每一个结点需要额外的内存保存前驱指针。
所有的操作需要更多的一个指针。

与单链表相比，删除与插入操作有的时候会更加便利，特别是当我们要删除给定指针指向的结点时。因为我们删除某个结点 p 的需要知道其前驱结点，而单链条并不能直接获取前驱结点。所以，为了找到前驱结点，我们要从头结点开始遍历链表，知道 p->next=q，说明 p 是 q 的前驱结点。

在 C 中的实现

// 结构体
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
}

// 创建新的结点，返回其指针
struct createNode(int data) {
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  temp->data = data;
  temp->prev = NULL;
  temp->next = NULL;
  return temp;
}

// 插入结点--在前面插入结点
void push(struct Node **head, int data) {
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  temp->data = data;
  temp->next = (*head);
  temp->prev = NULL;
  if((*head) != NULL) {
    (*head)->prev = temp;
  }
  (*head) = temp;
}

// 插入结点--在末尾插入结点
void append(struct Node** head, int data) {
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *head;
  temp->data = data;
  temp->next = NULL;
  if(*head == NULL) {
    temp->prev = NULL;
    *head = temp;
    return;
  }
  while(last->next != NULL) {
    last=last->next;
  }
  last->next = temp;
  temp->prev = last;
  return;
}

// 插入结点--在指定结点之后插入结点
void insertAfter(struct Node* refNode, int data) {
  if(refNode == NULL) {
    return;
  }
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  temp->data = data;
  temp->next = refNode->next;
  refNode->next = temp;
  temp->prev = refNode;
  if(temp->next != NULL) {
    temp->next->prev = temp;
  }
}

// 插入结点--在指定结点之前插入结点
void insertBefore(struct Node* refNode, int data) {
  if(refNode == NULL) return;
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  temp->data = data;
  temp->prev = refNode->prev;
  refNode->prev = temp;
  temp->next = refNode;
  if(temp->prev != NULL) {
    temp->prev->next = temp;
  }
}

// 删除结点--指定删除结点
void deleteNode(struct Node** head, struct Node *del) {
  if(*head==NULL || del == NULL) return;
  if(*head == del) *head = del->next;
  if(del->next != NULL) del->next->prev = del->prev;
  if(del->prev != NULL) del->prev->next = del->next;
  free(del);
  return;
}

// 删除结点--指定删除位置
void deleteNodeAt(struct Node** head, int position) {
  if(*head == NULL || position <= 0) return;
  struct Node* current = *head;
  int i;
  for(int i = 1;current != NULL && i <n; i++) {
    current = current->next;
  }
  if(current == NULL) return;
  deleteNode(head, current);
}

// 链表长度
int listLength(struct Node* node) {
  int len = 0;
  while(node != NULL) {
    len++;
    node = node->next;
  }
  return len;
}

// 颠倒双向链表
void reverse(struct Node **head) {
  struct Node *temp = NULL;
  struct Node *current = *head;
  while(current != NULL) {
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    current = current->prev;
  }
  if(temp != NULL) *head = temp->prev;
}

参考链接

geeksforgeeks: doublyLinkedList

# 数据结构之双向链表

与单链表的对比

在 C 中的实现

参考链接

# 数据结构之单链表

# 数据结构之栈