一、单向链表实现
在单向链表结构中，每个节点包含两部分，元素部分和指针部分，其中元素部分即为节点的值，指针部分指向下一个节点或者None，另外，为了找到第一个节点，需要定义一个头结点head，它只含有指针，即指向头元素或者None 。
类似于数组具有的增删查改等功能，我们希望单向链表具备这些基本功能，接下来开始自定义单向链表的基本功能。
"""定义节点""" class Node(): def __init__(self, item): self.item = item self.next = None """定义单向链表""" class SingleList(): """将头指针设为链表的私有属性""" def __init__(self, node=None): self.__head = node """判断是否为空""" def is_Empty(self): return self.__head == None """ 链表长度,通过遍历获得 需要考虑特殊情况：链表为空时是否能够正确执行 """ def get_length(self): cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def traver(self): cur = self.__head while cur != None: print(cur.item, end=" ") cur = cur.next print() """ 头部添加元素 需要考虑特殊情况：链表为空时是否能够正确执行 """ def addFirst(self, item): node = Node(item) node.next = self.__head self.__head = node """ 尾部添加元素,首先需要遍历找到最后一个元素 需要考虑特殊情况：链表为空时是否能够正确执行 """ def addLast(self, item): node = Node(item) cur = self.__head if cur == None: self.__head = node else: while cur.next != None: cur = cur.next cur.next = node """ 在指定位置添加元素，先找到添加的位置 需要考虑特殊情况：在头部和尾部以及为空时能否正确执行 """ def insert(self, index, item): if index <= 0: self.addFirst(item) elif index >= self.get_length(): self.addLast(item) else: node = Node(item) cur = self.__head count = 1 while count < index: cur = cur.next count += 1 node.next = cur.next cur.next = node """ 查找元素 注意链表为空的特殊情况 """ def find(self, item): if self.is_Empty(): print("链表为空，无法查找") return cur = self.__head i = 0 while cur.next != None and not cur.item == item: cur = cur.next i += 1 if cur.item == item: return("找到了，元素%s在%d处" %(item, i)) else: return("没找到") """ 删除指定位置元素 """ def remove(self, index): if self.is_Empty(): print("链表为空，无法删除") return if index < 0 or index > self.get_length(): print("索引越界，请检查!") return cur = self.__head pre = None count = 0 if index == 0: self.__head = cur.next return else: while count != index: pre = cur cur = pre.next count += 1 pre.next = cur.next return if __name__ == "__main__": sl = SingleList() print(sl.is_Empty()) sl.find(7) sl.insert(0,9) sl.traver() sl.addFirst(1) sl.traver() sl.addLast(2) sl.addLast(3) sl.addLast(4) sl.addLast(5) sl.addLast(6) sl.traver() sl.insert(-2, 21) sl.traver() sl.insert(20, 25) sl.traver() sl.insert(0, 15) sl.traver() sl.insert(2, 17) sl.traver() print(sl.find(7)) print(sl.find(6)) sl.remove(3) sl.traver() sl.remove(0) sl.traver() sl.remove(-1) sl.traver() sl.remove(20) sl.traver()
测试结果为：
True 链表为空，无法查找 9 1 9 1 9 2 3 4 5 6 21 1 9 2 3 4 5 6 21 1 9 2 3 4 5 6 25 15 21 1 9 2 3 4 5 6 25 15 21 17 1 9 2 3 4 5 6 25 没找到 找到了，元素6在9处 15 21 17 9 2 3 4 5 6 25 21 17 9 2 3 4 5 6 25 索引越界，请检查! 21 17 9 2 3 4 5 6 25 索引越界，请检查! 21 17 9 2 3 4 5 6 25
单链表基本的增删改查等功能已基本实现，但代码还是有待改善优化