单链表

结点的组成键值指向下一结点的指针单链表使用的API#时间复杂度中有关对尾部操作的函数的时间复杂度粗体为有尾部的情况API说明时间复杂度PushFront(key)在链表首部插入元素O（1）key TopFront()key返回链表首部元素O(1)PopFront（）删除链表首部元素O(1)PushBack(key)

lym152898

728人浏览 · 2016-06-28 10:18:24

lym152898 · 2016-06-28 10:18:24 发布

结点的组成

键值
指向下一结点的指针

单链表使用的API

#时间复杂度中有关对尾部操作的函数的时间复杂度粗体为有尾部的情况

API	说明	时间复杂度
PushFront(key)	在链表首部插入元素	O（1）
key TopFront()key	返回链表首部元素	O(1)
PopFront（）	删除链表首部元素	O(1)
PushBack(key)	在链表尾部添加元素	O(n)/O(1)
key TopBack()	返回链表尾部元素	O(n)/O(1)
PopBack()	删除链表尾部元素	O(n)
Boolean Find(key)	判断key元素是否在链表中	O(n)
Erase(key)	从链表中删除key元素	O(n)
Boolean Empty()	判断链表是否为空	O(1)
AddBefore(Node, key)	在Node结点之前插入元素	O(n)
AddAfter(Node, key)	在Node结点之后插入元素	O(n)

伪代码实现

链表添加元素操作：添加元素之后要根据初始链表是否为空来更改头指针或者尾指针
链表删除元素：删除之前先判断链表是否为空，在判断删除之后链表是否为空来修改指针

PushFront(key)

PushFront(key)：
    node <--- new node  #创建新结点
    node.key <--- key   #修改键值
    node.next <--- head #更新头指针
    if tail = nil:      #判断初始链表是否为空
        tail <--- head

PopFront()

if head <--- nil        #判断链表是否为空
    ERROR:empty list
    head <--- head.next #修改头指针指向下一个指针
if head = nil           #判断删除后链表是否为空
   tail <--- nil        #若为空则更改尾指针

PushBack（key）

PushBack（key）:
    node <--- new node    #创建新结点
    node.key <--- key     #修改键值
    node.next <--- nil    #修改指针
    if tail = nil         #若链表为空
        head <--- tail <--- node
    else                  #若链表不为空，修改尾指针
        tail.next <--- node
        tail <--- node

PopBack（）

if head = nil
    ERROR:empty list
if head = tail
    head <--- tail <--- nil
else
    p <--- head
    while p.next.next != nil
         p <--- p.next
    p.next <--- nil
    tail <--- p

AddAfter(Node ,key)

AddAfter(Node ,key):
    node2 <--- new node
    node2.key <--- key
    node2.next <--- node.next
    node.next <--- node2
    if node = tail
        tail <--- node2