概念
鏈表（linked list）是一種常見的線性表結(jié)構(gòu)癌幕，在存儲(chǔ)單元上非連續(xù)拒名，非順序的存儲(chǔ)結(jié)構(gòu)中燥，由節(jié)點(diǎn)組成羽戒，節(jié)點(diǎn)可以在運(yùn)行中動(dòng)態(tài)生成缤沦，每一個(gè)節(jié)點(diǎn)中存放兩種信息：當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域，下一個(gè)節(jié)點(diǎn)的位置信息（指針域）易稠，需要說(shuō)明的是python中鏈表和棧都是自定義的數(shù)據(jù)結(jié)構(gòu)（需要自己定義實(shí)現(xiàn)）
image.png
- head：頭結(jié)點(diǎn)
- val：當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
- next：下一個(gè)節(jié)點(diǎn)的存放位置
- last：尾結(jié)點(diǎn)缸废，一般用tail表示
單向鏈表的實(shí)現(xiàn)：鏈表的頭插，尾插驶社，指定位置插入企量，頭刪，刪除指定元素亡电，獲取鏈表長(zhǎng)度届巩，打印鏈表所有元素，查找鏈表中指定元素
"""
鏈表：
"""
class ListNode(object):
def __init__(self, val, next):
self.val = val
self.next = next
class LinkedList(object):
def __init__(self):
self.head = None
#鏈表的頭插
def Headinsert(self, elem):
cur = ListNode(elem, None)
cur.next = self.head
self.head = cur
#鏈表的尾插
def append(self, elem):
if self.head == None:
self.Headinsert(elem)
else:
cur = self.head
while cur.next != None:
cur = cur.next
node = ListNode(elem, None)
cur.next = node
#指定位置插入元素
def insert(self, pos, val):
if pos <= 0:
self.Headinsert(val)
elif pos > self.len():
self.append(val)
else:
count = 0
cur = self.head
while count < pos - 1:
cur = cur.next
count += 1
node = ListNode(val, None)
tail = cur.next
cur.next = node
node.next = tail
#鏈表的頭刪
def Pophead(self):
if self.head == None:
return None
else:
cur = self.head.next
elem = self.head.val
self.head = None
self.head = cur
return elem
#刪除鏈表的指定元素
def remove(self, val):
if val == self.head.val:
self.Pophead()
else:
cur = self.head
#找到要?jiǎng)h除元素的前一個(gè)節(jié)點(diǎn)
while cur.next.val != val:
cur = cur.next
cur.next = cur.next.next
#查找節(jié)點(diǎn)
def search(self, val):
if self.head == None:
return False
cur = self.head
while cur != None:
if cur.val == val:
return True
else:
cur = cur.next
return False
#遍歷鏈表
def traval(self):
if self.head == None:
return None
cur = self.head
while cur != None:
print(cur.val)
cur = cur.next
#獲取鏈表長(zhǎng)度
def len(self):
if self.head == None:
return 0
cur = self.head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
if __name__ == '__main__':
lk = LinkedList()
# print(lk.len())
# lk.Headinsert(4)
# lk.Headinsert(5)
lk.Headinsert(6)
lk.insert(2, 3)
# lk.Headinsert(5)
# lk.append(10)
# lk.Pophead()
# lk.remove(6)
# lk.traval()
# print(lk.search(19))
print(lk.len())
單向循環(huán)鏈表:與單向鏈表的區(qū)別是：?jiǎn)蜗蜓h(huán)鏈表的尾節(jié)點(diǎn)指向頭結(jié)點(diǎn)
#創(chuàng)建節(jié)點(diǎn)
class ListNode(object):
#初始化節(jié)點(diǎn)的元素
def __init__(self, val):
self.val = val
self.next = None
#創(chuàng)建鏈表類
class LinkList(object):
def __init__(self):
self.head = None
self.tail = None
#獲取鏈表的長(zhǎng)度
def len(self):
if self.head == None:
return 0
else:
cur = self.head
count = 0
while cur.next != self.head:
cur = cur.next
count += 1
return count + 1
#頭插
def insertHead(self, val):
node = ListNode(val)
if self.head == None:
self.head = node
node.next = self.head
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
node.next = self.head
self.head = node
#尾插
def append(self, data):
node = ListNode(data)
if self.head == None:
self.head = node
node.next = self.head
else:
node.next = self.head
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
#指定位置插入
def insert(self, pos, val):
node = ListNode(val)
if pos <= 0:
self.head = node
node.next = self.head
elif pos > self.len():
self.append(val)
else:
cur = self.head
count = 0
while count < pos - 1:
cur = cur.next
count += 1
tail = cur.next
cur.next = node
node.next = tail
#頭刪
def pop(self):
if self.head == None:
return None
else:
if self.len() <= 1:
ele = self.head.val
self.head = None
return ele
else:
cur = self.head
ele = self.head.val
while cur.next != self.head:
cur = cur.next
new_head = self.head.next
self.head = new_head
cur.next = new_head
return ele
#尾刪
def tailDel(self):
if self.head == None:
return None
else:
if self.len() <= 1:
ele = self.head.val
self.head = None
return ele
else:
cur = self.head
count = 1
while count < self.len() - 1:
cur = cur.next
count += 1
ele = cur.next.val
cur.next = self.head
return ele
#刪除指定位置元素
def remove(self, pos):
if self.head == None:
return None
else:
if pos <= 0:
self.pop()
elif pos >= self.len():
self.tailDel()
else:
cur = self.head
count = 0
while count < pos - 1 :
cur = cur.next
count += 1
ele = cur.next.val
cur.next = cur.next.next
return ele
# 打印鏈表
def traval(self):
res = []
if self.head == None:
return res
cur = self.head
res.append(cur.val)
while cur.next != self.head:
cur = cur.next
res.append(cur.val)
return res
if __name__ == '__main__':
lk = LinkList()
lk.insertHead(3)
# lk.insertHead(4)
# lk.insert(2, 10)
lk.append(4)
lk.insertHead(10)
# lk.tailDel()
# print(lk.pop())
# lk.remove()
lk.remove(1)
print(lk.traval())
print(lk.len())
雙向鏈表：有兩個(gè)指針份乒，一個(gè)指向next恕汇，一個(gè)指向pre
"""
雙向鏈表
"""
class ListNode():
def __init__(self, val):
self.next = None
self.pre = None
self.val = val
class DoubleLinkList():
def __init__(self):
self.head = None
self.length = 0
#頭插
def insert(self, val):
node = ListNode(val)
if self.head == None:
self.head = node
else:
node.next = self.head
self.head.pre = node
self.head = node
self.length += 1
#尾插
def append(self, val):
node = ListNode(val)
if self.head == None:
self.head = node
else:
cur = self.head
while cur.next != None:
cur = cur.next
node = ListNode(val)
cur.next = node
node.pre = cur
self.length += 1
#指定位置插入
def insertIndex(self, pos, val):
if pos <= 0:
self.insert(val)
elif pos >= self.length:
self.append(val)
else:
count = 0
cur = self.head
while count < pos - 1:
cur = cur.next
count += 1
node = ListNode(val)
node.next = cur.next
cur.next.pre = node
node.pre = cur
cur.next = node
self.length += 1
#頭刪
def pop(self):
if self.head == None:
return None
else:
cur = self.head
ele = cur.val
self.head = cur.next
self.head.pre = None
self.length -=1
return ele
#尾刪
def remove(self):
if self.head == None:
return None
else:
cur = self.head
while cur.next != None:
cur = cur.next
ele = cur.val
cur.pre.next = None
self.length -= 1
return ele
#指定位置刪除
def popIndex(self, pos):
if pos <= 0:
self.pop()
elif pos >= self.length:
self.remove()
else:
count = 0
cur = self.head
while count < pos:
cur = cur.next
count += 1
ele = cur.val
cur.next.pre = cur.pre
cur.pre.next = cur.next
self.length -= 1
return ele
#遍歷鏈表
def traval(self):
res = []
if self.head == None:
return res
else:
cur = self.head
while cur != None:
res.append(cur.val)
cur = cur.next
return res
if __name__ == '__main__':
lk = DoubleLinkList()
# lk.insert(3)
# lk.insert(4)
lk.insert(5)
lk.append(10)
lk.insertIndex(1, 20)
# lk.pop()
# lk.remove()
# lk.pop()
lk.popIndex(0)
print(lk.traval())
print(lk.length)
