单链表的实现单链表的实现

关于单链表
文章图片
single-link-list.jpg
代码实现

class Node(object): """节点""" def __init__(self, elem): self.elem = elem self.next = Noneclass SingleLinkList(object): """单链表""" def __init__(self, node = None): self.__head = nodedef is_empty(self): """链表是否为空""" return self.__head == Nonedef length(self): """链表长度""" # cur游标，用来移动遍历节点 cur = self.__head # count记录数值 count = 0 while cur != None: count += 1 cur = cur.next return countdef travel(self): """遍历整个链表""" cur = self.__head while cur != None: print(cur.elem, end = " ") cur = cur.next print("")def add(self, item): """链表头部添加元素，头插法""" #此处必须先将head之后的元素和要插入元素的节点连接，然后再把插入元素连接到head上 #head先与要插入元素连接的话，那么head原来后面的元素就会找不到head的存在，那么后续节点都会丢失 #此处是重点 node = Node(item) node.next = self.__head #此处就是先将head之后的节点指向要插入元素的next self.__head = node#然后再将插入元素指向headdef append(self, item): """链表尾部添加元素，尾插法""" node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = nodedef insert(self, pos, item): """指定位置添加元素""" #pos是从零开始 #insert(2, 100)这句话意思是把100添加到原先的链表的1之后，2之前，原先的2变成3 #如果说cur指的是当前的游标，那么此处就用pre来表示 #因为需要找到pos之前的那一个位置 #跟add的操作一样 #先将pre.next指向要插入元素的next #然后再将要插入数据的节点指向pre.next 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 = nodedef remove(self, item): """删除节点""" cur = self.__head pre = None while cur != None: if cur.elem == item: #先判断当前节点是否头节点 #怎么判断 if cur == self.__head: self.__head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next #此处必须先将pre移动到cur的位置 #然后再将cur移到下一个位置 #如果步骤相反的话，先移动cur到下一个位置，再移动pre到cur位置，那么会出现两位置同步def search(self, item): """查找节点是否存在""" cur = self.__head while cur != None: if cur.elem == item: return True else: cur = cur.next return Falseif __name__ == "__main__": ll = SingleLinkList() print(ll.is_empty()) print(ll.length())ll.append(1) print(ll.is_empty()) print(ll.length())ll.add(8) ll.append(2) ll.append(3) ll.append(4) ll.append(5) ll.append(6) ll.travel() ll.insert(-1, 9) ll.travel() ll.insert(3, 100) ll.travel() ll.insert(10, 200) ll.travel() ll.remove(100) ll.travel() ll.remove(9) ll.travel() ll.remove(200) ll.travel()

/Library/Frameworks/Python.framework/Versions/3.6/bin/python3.6 /Users/xinqi/PycharmProjects/test/test.py True 0 False 1 8 1 2 3 4 5 6 9 8 1 2 3 4 5 6 9 8 1 100 2 3 4 5 6 9 8 1 100 2 3 4 5 6 200 9 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 Process finished with exit code 0