-
關(guān)于單鏈表single-link-list.jpg
- 代碼實現(xiàn)
class Node(object):
"""節(jié)點(diǎn)"""
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游標(biāo)，用來移動遍歷節(jié)點(diǎn)
cur = self.__head
# count記錄數(shù)值
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之后的元素和要插入元素的節(jié)點(diǎn)連接，然后再把插入元素連接到head上
#head先與要插入元素連接的話，那么head原來后面的元素就會找不到head的存在，那么后續(xù)節(jié)點(diǎn)都會丟失
#此處是重點(diǎn)
node = Node(item)
node.next = self.__head #此處就是先將head之后的節(jié)點(diǎn)指向要插入元素的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指的是當(dāng)前的游標(biāo)，那么此處就用pre來表示
#因為需要找到pos之前的那一個位置
#跟add的操作一樣
#先將pre.next指向要插入元素的next
#然后再將要插入數(shù)據(jù)的節(jié)點(diǎn)指向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
#當(dāng)循環(huán)結(jié)束后，pre指向pos-1的位置
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""刪除節(jié)點(diǎn)"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
#先判斷當(dāng)前節(jié)點(diǎn)是否頭節(jié)點(diǎn)
#怎么判斷
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位置，那么會出現(xiàn)兩位置同步
def search(self, item):
"""查找節(jié)點(diǎn)是否存在"""
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
