链表的基本知识

链式结构的存储

• 用一种任意存储单元存储数据元素

• 各个存储单元在内存中可以不用连续

• 通过指针的形式链接起来

单项链表

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对于每个数据元素ai，除了存储本身的信息外，还需要存储一个指示其直接后继的信息（后继的存储位置-地址）。

存储数据元素信息的域称为数据域，存储直接后继位置的域称为指针域，指针域中存储的信息称为指针或链。

这两部分信息组成数据元素ai的存储映像，称为结点。

• 多个节点相连

• 每个节点中包含一个数据域和一个指针域

• 单链表的指针域指向的是下一个节点的地址

• 把指向下个节点的指针叫做后继指针

• 单链表的第一个节点的存储位置叫做头指针，最后一个节点的后继指针为空

• 各个存储单元在内存中可以不用连续

• 通过指针的形式链接起来

• 此外，有时候为了操作，我们会在第一个节点前面添加一个节点，称为头节点

• 头指针和和头节点

• 头指针是指向链表第一个节点的指针，头指针在链表中必须存在，因为我们要通过头指针直到链表的位置在哪里

  如果存在头节点，那么头指针就是指向头节点的指针，其实和上面一样，有头节点的话，第一个节点必是头指针

• 头节点不具有实际意义，头节点中不存储数据元素，只是我们在删除或者插入时，为了统一头节点的操作专门设定的

单向链表的插入操作

• 单项链表插入操作

• 如上图，如果将t节点插入到s节点后需要
  • 将t节点的后继节点指向s节点的后继节点
  • 将s节点的后继节点指向节点t
• 单项链表的删除操作

• 由图可见，删除操作的本质其实是绕过要删除的节点，这里指t节点
• 具体操作是将节点s的后继指针指向节点t的后继指针

双向链表

• 双向链表，有两个方向，相对于单向链表，多了一个前驱指针prev,指向前驱节点
• 双向链表可以向前走，也可以向后

• 双向链表用了空间换时间，会更快

单项链表和双向链表操作对比

链表的插入的两种前置条件

• 在data域的某个特定值的节点前后插入新的节点

• 在给定的节点前后插入新的节点

• 针对第一种情况，两种链表的复杂度相近

  • 第一步显示表里链表找到值为特定值的节点，两种都是从头开始遍历复杂度O(n)

  

  • 第二步是插入操作
    • 如果是向后插入，那么两种链表时间复杂度基本一直
    • 如果是向前插入，单链表慢，因为单链表还需要再遍历一次链表找到特定值节点的前驱节点这个时间又是O(n)，但是双向链表可以直接找到前驱节点

  

• 针对第二种情况，和第一种类似，已经知道节点的情况下如果向后插入，单链表和双链表没有区别 都是O(1)

• 针对第二种情况，如果向前插入，单链表需要循环链表，找到先找到前驱节点，而双向链表可以直接插入

两种链表的删除操作

两种前置条件

- 在某个data域值等于特定值前后删除
- 在某个节点前后删除

• 对于情况一

  • 第一步，需要在data域值找到特定值节点，这一步两种链表相同
  • 如果是向前删除，那么单向链表需要再遍历一次链表，找到特定值节点的前驱节点，而双向链表可以直接删除
  • 如果是向后删除，两者时间复杂度相似

• 针对情况二：

  • 如果是向前删除，单向链表需要遍历，找到前驱节点才可以删除，双向链表可以直接利用prev指针
  • 如果是向后删除，两者时间复杂度相似

• 此外，有时候为了操作，我们会在第一个节点前面添加一个节点，称为头节点

• 头指针和和头节点

• 头指针是指向链表第一个节点的指针，头指针在链表中必须存在，因为我们要通过头指针直到链表的位置在哪里

  如果存在头节点，那么头指针就是指向头节点的指针，其实和上面一样，有头节点的话，第一个节点必是头指针

• 头节点不具有实际意义，头节点中不存储数据元素，只是我们在删除或者插入时，为了统一头节点的操作专门设定的