双向链表

概念

双向链表的每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

 指向前一节点的链接区可以自己命名，叫做prev，指向后一节点的链接区叫做next。

 在双向链表中，游标对应的节点的前一个节点叫做“前驱节点”，后一个节点叫做“后继节点”。

双向链表的结构如下

操作（同单向链表）

• is_empty() 链表是否为空
• length() 链表长度
• travel() 遍历链表
• add(item) 链表头部添加
• append(item) 链表尾部添加
• insert(pos, item) 指定位置添加
• remove(item) 删除节点
• search(item) 查找节点是否存在

定义节点类——多了一个self.prev

class Node(object):
    """节点"""
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.prev = None

定义双链表类（构造函数、判空、链表长度、遍历链表这些操作同单向链表）

class DoubleLinkList(object):
    """双链表"""
    def __init__(self):
        self.__head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head is None

    def length(self):
        """链表长度"""
        # cur是一个“游标”（或指针也可），初始时指向头节点
        cur = self.__head
        count = 0
        # 尾节点指向None，当未到达尾部时
        while cur is not None:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self.__head
        while cur != None:
            print(cur.item, end=" ")
            cur = cur.next
        print(" ")

    # 上面的都不需要改变

在头部添加元素add(item)

 头部添加元素，在改变链接区指向的时候可以有不同的先后顺序，注意不同顺序的逻辑关系

    def add(self, item):
        """头部添加元素"""
        # 先创建一个保存item值的节点
        node = Node(item)
        # 将新节点的链接域next指向头节点，即_head指向的位置
        node.next = self.__head
        # 将链表的头_head指向新节点
        self.__head = node
        node.next.prev = node
        # 还可以有下面的等效操作，先将新节点链接域指向头节点，然后将头节点的prev连到新节点上，最后再将_head指向新节点
        # node.next = self.__head
        # self.__head.prev = node
        # self.__head = node

在尾部添加元素append(item)

    def append(self, item):
        """尾部添加元素"""
        node = Node(item)
        # 先判断链表是否为空，若是空链表，则将_head指向新节点
        if self.is_empty():
            self.__head = node  # 这里不需要改变，node.prev指向None
        # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur  # 增加这一句即可

指定位置添加

两种方式都可，但是要注意先后顺序及逻辑

    def insert(self, pos, item):
        """指定位置添加元素"""
        # 若指定位置pos为第一个元素之前，则执行头部插入
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾部插入
        elif pos > (self.length() - 1):
            self.append(item)
        # 找到指定位置
        else:
            cur = self.__head
            count = 0
            # cur游标指向指定位置pos
            while count < pos:
                count += 1
                cur = cur.next
            # 先将新节点node的next指向插入位置的节点
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            cur.prev = node  # 先将后继节点的prev指向node
            node.prev.next = cur  # 再将前驱节点的next指向node，因为此时前驱节点已经变为node.prev，所以就是node.prev.next = cur
            # 同理也有两种形式
            # node.next = cur
            # node.prev = cur.prev
            # cur.prev.next = node  # 先将前驱节点的next指向node，当然此时也可以用node.prev.next = node，因为上一句已经node.prev = cur.prev了
            # cur.prev = node  # 再将后继节点的prev指向node

查找search(item)

也和单链表一样

    # 查找操作和单链表也是一样的
    def search(self, item):
        """链表查找节点是否存在，并返回True或者False"""
        cur = self.__head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

删除元素remove(item)

删除元素的时候有几种特殊情况需要注意

1. 元素在头节点
   1. 如果在头节点的话还要判断一下是否只有一个节点
2. 元素在尾节点

    def remove(self, item):
        """删除节点"""
        cur = self.__head
        while cur != None:
            # 找到了指定元素
            if cur.elem == item:
                # 先判断此节点是否是头节点
                # 头节点
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next:
                        # 判断链表是否只有一个节点
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                break
            else:
                # 继续按链表后移节点
                cur = cur.next

单向循环链表

概念

与单向链表唯一的区别就在于单向循环链表的尾节点的next域指向头节点形成一个循环

操作（同单向链表）

定义节点类和单向循环链表类

单向循环链表的构造函数和单向链表的构造函数有些区别

class Node(object):
    """单链表的结点"""
    def __init__(self, item):
        # _item存放数据元素
        self.elem = item
        # _next是下一个节点的标识
        self.next = None



class SingleCycleLinkList(object):
    """单向循环链表"""
    def __init__(self, node=None):
        self.__head = node
        if node:
            node.next = node

判空is_empty()

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None

链表长度length()

    def length(self):
        """链表长度"""
        # cur是一个“游标”（或指针也可），初始时指向头节点
        cur = self.__head
        if self.is_empty():
            return 0
        count = 1   # count从1开始
        while cur.next != self.__head:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

遍历travel()

    def travel(self):
        """遍历链表"""
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem, end=" ")
            cur = cur.next
        # 退出循环，cur指向尾节点，但此时尾节点元素未打印
        print(cur.elem)

在头部添加元素add(item)

    def add(self, item):
        """头部添加元素"""
        # 先创建一个保存item值的节点
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # 退出循环，cur指向尾节点
            node.next = self.__head
            self.__head = node
            cur.next = self.__head

特殊情况需要注意

• 空链表

尾部添加元素append(item)

    def append(self, item):
        """尾部添加元素"""
        node = Node(item)
        # 先判断链表是否为空，若是空链表，则将_head指向新节点
        if self.is_empty():
            self.__head = node
            node.next = node
        # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # node.next = cur.next
            node.next = self.__head
            cur.next = node

任意位置插入元素insert(item)

同单向链表，不需要更改

    def insert(self, pos, item):
        """指定位置添加元素"""
        # 若指定位置pos为第一个元素之前，则执行头部插入
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾部插入
        elif pos > (self.length() - 1):
            self.append(item)
        # 找到指定位置
        else:
            node = Node(item)
            count = 0
            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
            pre = self.__head
            while count < (pos - 1):
                count += 1
                pre = pre.next
            # 先将新节点node的next指向插入位置的节点
            node.next = pre.next
            # 将插入位置的前一个节点的next指向新节点
            pre.next = node

查找research(item)

    def search(self, item):
        """链表查找节点是否存在，并返回True或者False"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            return True
        return False

注意特殊情况——空链表

退出循环的时候cur指向尾节点，没有在循环中比较cur.elem 与 item的值，所以在循环外还需要进行一次比较

删除节点remove(item)

    def remove(self, item):
        """删除节点"""
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                # 先判断此节点是否是头节点
                if cur == self.__head:
                    # 头节点的情况
                    # 找尾节点
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 中间节点
                    pre.next = cur.next
                return
            else:
                # 继续按链表后移节点
                pre = cur
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            if cur == self.__head:
                # 链表只有一个节点
                self.__head = None
            else:
                pre.next = cur.next

注意若所删除的节点位于中间位置，退出循环删除完毕之后要使用return语句而不是像单向链表的break语句，否则会报错！

单向循环链表的remove()需要注意的地方比较多

• 是否是空链表？
• 所删元素位于头节点、中间节点和尾节点的处置均不相同
• 只有一个节点？——直接跳到最后一个if中，删除之后就没有节点了，__head指向None即可

链表扩展

不光是单向链表可以变成循环链表，双向链表也可以做成双向循环链表

另外，头部信息也可以加上