Python中链表的实现

writer：lIcht                      email：lIcht.gzl@gmail.com                 Date:  2019.9.14

        在对算法与数据结构的学习中，链表是线性表很基础的一种数据类型。在C语言等面向过程的语言中利用基础数据类型：int、char、str、float等实现单链表是必备的技能。而在Python中，除了基础的数据类型，自身也封装了多种高级数据类型：list、tuple、dict等为复杂程序的编写提供了很大的便捷。但是为了对数据结构进行进一步的理解，在Python中用基础数据类型使用面向对象的思想也可以类似C语言封装高级的自定义数据类型。

        这里使用链表这一简单的数据类型作为例子说明。将链表以及链表中的节点作为两个类，其中节点是小类，而链表则是管理节点之间关系的大类，为增、删、查、补节点提供方法和属性。下面给出源码以供理解。

xxxxxxxxxx
# 《单链表的实现》
# 用元组(elem, next)实现更加简单但是为了说明问题
# 这里把节点抽象出来作为一个类
# 在这之上创建单链表大类对节点对象进行操作
​
​
class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None
​
# node = Node(1)
​
​
class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node
​
    def is_empty(self):
        """链表是否为空"""
        # 头链接未指向任何位置，则为空
        return self.__head is None
​
    def length(self):
        """链表长度"""
        # cur指针，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count
​
    def travel(self):
        """遍历整个链表"""
        # cur指针，用来移动遍历节点
        cur = self.__head
        # count记录数量
        while cur is not None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("\n")
​
    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 is not None:
                cur = cur.next
            cur.next = node
​
    def insert(self, pos, item):
        """指定位置添加元素"""
        cur = self.__head
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
​
        else:
            # count记录数量
            count = 0
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 当pre循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next = cur.next
            cur.next = node
​
    def remove(self, item):
        """删除节点"""
        if self.search(item) is False:
            print("链表中无此节点")
        else:
            if self.__head.elem == item:
                self.__head = self.__head.next
            else:
                cur = self.__head
                while cur is not None:
                    if cur.next.elem == item:
                        cur.next = cur.next.next
                        break
                    cur = cur.next
​
    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
        while cur is not None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False
​
​
if __name__ == "__main__":
    # 演示
    li = SingleLinkList()
    print(li.is_empty())
    print(li.length())
    li.append(3)
    li.travel()
    li.remove(3)
    li.travel()
    li.append(5)
    li.travel()
    li.insert(1, 7)
    li.travel()
​

xxxxxxxxxx
# 《双向链表的实现》
class Node(object):
    """双向链表节点"""
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.prev = 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指针，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count
​
    def travel(self):
        """遍历整个链表"""
        # cur指针，用来移动遍历节点
        cur = self.__head
        # count记录数量
        while cur is not None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("\n")
​
    def add(self, item):
        """链表头部添加元素，头插法"""
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.prev = node
​
    def append(self, item):
        """链表尾部添加元素，尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prev = cur
​
    def insert(self, pos, item):
        """指定位置添加元素"""
        cur = self.__head
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
​
        else:
            # count记录数量
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            # 当cur循环退出后，cur指向pos位置
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            node.prev.next = node
            cur.prev = node
​
    def remove(self, item):
        """删除节点"""
        if self.search(item) is False:
            print("链表中无此节点")
        else:
            if self.__head.elem == item:
                self.__head = self.__head.next
            else:
                cur = self.__head
                while cur is not None:
                    if cur.elem == item:
                        cur.prev.next = cur.next
                        if cur.next:
                            cur.next.prev = cur.prev
                        break
                    cur = cur.next
​
    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
        while cur is not None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False
​
​
if __name__ == "__main__":
    # 演示
    li = DoubleLinkList()
    print(li.is_empty())
    print(li.length())
    li.append(3)
    li.travel()
    li.remove(3)
    li.append(5)
    li.travel()
    li.insert(1, 7)
    li.travel()
​

xxxxxxxxxx
# 《单向循环链表的实现》
​
​
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指针，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count
​
    def travel(self):
        """遍历整个链表"""
        if self.is_empty():
            return
        # cur指针，用来移动遍历节点
        cur = self.__head
        # count记录数量
        while cur.next != self.__head:
            print(cur.elem, end=" ")
            cur = cur.next
        # 退出循环cur指向尾节点，但尾节点的元素未打印
        print(cur.elem)
        print("\n")
​
    def add(self, item):
        """链表头部添加元素，头插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
            return
        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
        # 退出循环，cur指向尾节点
        node.next = self.__head
        self.__head = node
        cur.next = self.__head
​
    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):
        """指定位置添加元素"""
        cur = self.__head
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
​
        else:
            # count记录数量
            count = 0
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 当pre循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next = cur.next
            cur.next = node
​
    def remove(self, item):
        """删除节点"""
        if self.search(item) is False:
            # 判断链表中有无此节点
            print("链表中无此节点")
            return
        else:
            if self.__head.elem == item:
                # 删除头节点的情况
                # 只有一个节点的情况
                if self.length() == 1:
                    self.__head = None
                    return
                # 不止一个节点的情况
                else:
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    rear.next = self.__head
            else:
                # 删除中间以及尾节点的情况
                cur = self.__head
                while cur.next != self.__head:
                    if cur.next.elem == item:
                        cur.next = cur.next.next
                        return
                    cur = cur.next
                if cur.next.elem == item:
                    cur.next = cur.next.next
​
    def search(self, item):
        """查找节点是否存在"""
        if self.__head is None:
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        if cur.elem == item:
            return True
        return False
​
​
if __name__ == "__main__":
    # 演示
    li = SingleCycleLinkList()
    print(li.is_empty())
    print(li.length())
    li.append(3)
    li.travel()
    li.remove(3)
    li.travel()
    li.append(5)
    li.travel()
    li.insert(0, 7)
    li.travel()
​