-
关于单链表single-link-list.jpg
- 代码实现
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 == None
def length(self):
"""链表长度"""
# cur游标，用来移动遍历节点
cur = self.__head
# count记录数值
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def 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 #然后再将插入元素指向head
def 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 = node
def 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 = node
def 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 False
if __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
-
链表和顺序表的对比
对比.jpg
