用python实现单链表的基础操作

1 问题

用python实现单链表的基础操作：插入，删除，遍历，判空，清空链表，求长度，获取元素，判断元素是否存在。

2 方法

解决问题的步骤采用如下方式：

1. 使用函数和类的方法来实现单链表的基本操作

2. 插入操作时使用头插法

3. 删除操作时，删除头节点一行代码即可，其他位置的需要判断+遍历

通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。

代码清单 1

class Node:    """链表节点初始化"""    def __init__(self, item):        self.item = item        self._next = None class LinkList:    """链表及其相关操作"""    def __init__(self):        self._head = None    def is_empty(self):        """判断是否为空链表，头节点为None则是空"""        return self._head is None    def length(self):        """求链表的长度"""        p = self._head        count = 0        while p:            count += 1            p = p._next        return count    def append(self, item):        """向链表尾部添加元素, 考虑是否是空链表"""        node = Node(item)        p = self._head        if not p:            self._head = node        else:            while p._next:                p = p._next            p._next = node    def add(self, item):        """向链表头部插入元素"""        node = Node(item)        node._next = self._head        self._head = node    def insert(self, position, item):        """向链表中插入元素"""        # 头插 or 尾插 or 中间插入        if position <= 0:            self.add(item)        elif position >= self.length():            self.append(item)        else:            pre = self._head            count = 0            while count < position - 1:                count += 1                pre = pre._next            node = Node(item)            node._next = pre._next            pre._next = node    def get_item(self, position):        """获取某位置的元素"""        if position < 0 or position >= self.length():            return None        p = self._head        count = 0        while count != position:            p = p._next            count += 1        return p.item    def exixt_value(self, item):        """某个值是否存在"""        p = self._head        while p:            if p.item == item:                return True            else:                p = p._next        return False    def remove(self, item):        """删除元素"""        p = self._head        pre = None        while p:            if p.item == item:                # 是否头节点                if not pre:                    self._head = p._next                else:                    pre._next = p._next                    break            else:                pre = p                p = p._next    def clear(self):        """删除链表"""        self._head = None    def travel(self):        """列表遍历"""        p = self._head        while p:            print(p.item, end=" ")            p = p._next        print() if __name__ == '__main__':    linklist = LinkList()    linklist.append(2)    linklist.append(3)    linklist.append(4)    linklist.append(5)    print(linklist.length())      linklist.travel()      linklist.add(1)    linklist.add(0)    linklist.travel()      linklist.insert(2, 8)    linklist.insert(2, 9)    linklist.travel()      print(linklist.get_item(2), linklist.get_item(12), linklist.get_item(4))        print(linklist.exixt_value(9), linklist.exixt_value(20))        linklist.remove(9)    linklist.remove(5)    linklist.travel()      linklist.clear()    linklist.travel()

3 结语

针对用python实现单链表的基础操作，通过python运行实验，证明该方法是有效的，这种设置方法代码较多，因此未来还需继续改善这种方法以适应更多场景。