python之链表、单链表、双向链表、单向循环链表

链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时，又需要进行数据的搬迁，所以使用起来并非很灵活

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理

链表定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）

即在申请储存单元的时候，对单个的单元进行拓展，不仅保留该数据，还要保留另外的一部分数据，这两部分称为一个整体，叫做节点。其中第一部分保存数据，第二部分保存地址。而为了链接200和400这两个节点，就将第一个节点的链接区储存为400的地址，后面执行相同的步骤，这样就达到了一种线性关系，通过构建这样的一种数据结构来达到这样的链接关系。
 

单向链表

单项链表也叫单链表，是链表中最简单的一种形式，他的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

单向链表的操作

具体操作包括：

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

单向链表实现

class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem  # 存放数据元素
        self.next = None  # 指向下一个节点的标识，对于下一个节点的初始状态指向空，因为不知道指向谁


class SingleLinkList(object):
    """单链表"""

    def __init__(self, node=None):
        self.__head = node

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

    def length(self):
        #  返回链表的长度
        cur = self.__head  # cur 游标，用于移动遍历节点
        count = 0  # 记录节点数量
        while cur:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        #  遍历链表
        cur = self.__head
        while cur:
            print(cur.elem, end=' ')
            cur = cur.next

    def add(self, item):
        #  链表头部添加元素，头插法
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        #  链表尾部添加元素， 尾插法
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        #  指定位置插入元素
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            #  当循环退出后，pre指向pos-1
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def search(self, item):
        #  查找节点是否存在
        cur = self.__head
        while cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

    def remove(self, item):
        #  删除元素
        #  要考虑链首、尾、为空
        cur = self.__head
        pre = None  # 游标cur的前一个节点
        while cur:
            if cur.elem == item:
                #  先判断该节点是否为头节点
                if cur == self.__head:
                    self.__head = cur.next  # 当只有头结点，将其删除后，self.__head就该是None，而cur.next就是None
                else:
                    """
                        注意：pre本身原是无节点意义的，是因为在判断条件下会先经历
                        pre = cur cur = cur.next 的位置后移，所以pre也有了和cur一样的节点属性！
                    """
                    pre.next = cur.next  # 把待删除节点的下个节点指给待删除节点的前个节点
                break  # 必须有
            else:
                pre = cur
                cur = pre.next  # pre与cur同时后移


if __name__ == '__main__':
    l1 = SingleLinkList()
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    l1.append(1)
    l1.append(2)
    l1.add(5)
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()
    l1.insert(-1, 8)
    l1.insert(3, 9)
    l1.insert(100, 200)
    print('\n判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()
    print('\n查找链表元素：', l1.search(5))
    print('删除链表元素：', l1.remove(2))
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()

运行结果：

链表和顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了节点的指针域，空间开销大，但对储存空间的使用要相对灵活。

链表域顺序表的各种操作复杂度如下所示：

注意虽然表面上看起来复杂度都是O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝和覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作之间的元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。

双向链表

一种更复杂的链表叫“双向链表”或者“双面链表”，每个节点有两个链接，一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

双向链表实现

class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem  # 存放数据元素
        self.next = None
        self.pre = None


class DoubleLinkList(object):
    """双链表"""

    def __init__(self, node=None):
        self.__head = node

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

    def length(self):
        #  返回链表的长度
        cur = self.__head  # cur 游标，用于移动遍历节点
        count = 0  # 记录节点数量
        while cur:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        #  遍历链表
        cur = self.__head
        while cur:
            print(cur.elem, end=' ')
            cur = cur.next

    def add(self, item):
        #  链表头部添加元素，头插法
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.pre = node

    def append(self, item):
        #  链表尾部添加元素， 尾插法
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next:
                cur = cur.next
            cur.next = node
            node.pre = cur

    def insert(self, pos, item):
        #  指定位置插入元素
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            #  当循环退出后，pre指向pos-1
            node = Node(item)
            node.next = cur
            node.pre = cur.pre
            cur.pre.next = node
            cur.pre = node

    def search(self, item):
        #  查找节点是否存在
        cur = self.__head
        while cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

    def remove(self, item):
        #  删除元素
        #  要考虑链首、尾、为空
        cur = self.__head
        while cur:
            if cur.elem == item:
                #  先判断该节点是否为头节点
                if cur == self.__head:
                    self.__head = cur.next  # 当只有头结点，将其删除后，self.__head就该是None，而cur.next就是None
                    if cur.next:  # 当只有cur这一个节点的时候，cur.next为None，是没有prev的
                        cur.next.pre = None
                else:
                    cur.pre.next = cur.next  # 把待删除节点的下个节点指给待删除节点的前个节点
                    if cur.next:
                        cur.next.pre = cur.pre
                break  # 必须有
            else:
                cur = cur.next  # pre与cur同时后移


if __name__ == '__main__':
    l1 = DoubleLinkList()
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    l1.append(1)
    l1.append(2)
    l1.add(5)
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()
    l1.insert(-1, 8)
    l1.insert(3, 9)
    l1.insert(100, 200)
    print('\n判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()
    print('\n查找链表元素：', l1.search(5))
    print('删除链表元素：', l1.remove(2))
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()

运行结果：

单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

单向循环链表实现

class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem  # 存放数据元素
        self.next = None  # 指向下一个节点的标识


class SingleCycleLinkList(object):
    """单向循环链表"""

    def __init__(self, node=None):
        self.__head = node
        if node:
            node.next = node

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

    def length(self):
        #  返回链表的长度
        if self.is_empty():
            return 0
        cur = self.__head  # cur 游标，用于移动遍历节点
        count = 0  # 记录节点数量
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        #  添上最后一个节点
        if cur.next == self.__head:
            count += 1
        return count

    def travel(self):
        #  遍历链表
        if self.is_empty():
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem, end=' ')
            cur = cur.next
        #  添上最后一个节点
        if cur.next == self.__head:
            print(cur.elem, end=' ')

    def add(self, 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 = node

    def append(self, 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.next = node
            node.next = self.__head

    def insert(self, pos, item):
        #  指定位置插入元素
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            #  当循环退出后，pre指向pos-1
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def search(self, item):
        #  查找节点是否存在
        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.next == item:
            return True
        return False

    def remove(self, item):
        #  删除元素
        #  要考虑链首、尾、为空
        if self.is_empty():
            return False
        cur = self.__head
        pre = None  # 游标cur的前一个节点
        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  # 把待删除节点的下个节点指给待删除节点的前个节点
                break  # 必须有
            else:
                pre = cur
                cur = pre.next  # pre与cur同时后移
        #  退出循环时，cur指向尾节点
        if cur.elem == item:
            if cur == self.__head:
                #  链表只有一个节点
                self.__head = None
            else:
                pre.next = cur.next


if __name__ == '__main__':
    l1 = SingleCycleLinkList()
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    l1.append(1)
    l1.append(2)
    l1.append(3)
    l1.add(5)
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()
    l1.insert(-1, 8)
    l1.insert(3, 9)
    l1.insert(100, 200)
    print('\n判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()
    print('\n查找链表元素：', l1.search(5))
    print('删除链表元素：', l1.remove(2))
    print('判断链表是否为空：', l1.is_empty())
    print('此时链表的长度为：', l1.length())
    print('遍历链表：', end=' ')
    l1.travel()

运行结果：