实现简易版本的双向不循环链表和单向循环链表。定义了头插、尾插、任意位置插入、删除和查找函数接口。
双向链表class Node():
def __init__(self, data):
self.data = data
self.pre = None
self.next = None
class DoublelinkList():
def __init__(self):
self._head = None
self._end = None
def add(self, data):
node = Node(data)
if self._head is None:
self._head = node
node.pre = None
else:
node.next = self._head
node.pre = None
self._head.pre = node
self._head = node
self._end = node
def append(self, data):
node = Node(data)
cur = self._head
while cur and cur.next:
cur = cur.next
if cur is None:
self.add(data)
else:
cur.next = node
node.pre = cur
self._end = node
def get_size(self):
cur = self._head
cnt = 0
while cur:
cur = cur.next
cnt += 1
return cnt
def insert(self, data, pos):
node = Node(data)
cur = self._head
pre = None
if pos <= 0:
self.add(data)
elif pos >= self.get_size():
self.append(data)
else:
while pos:
pre = cur
cur = cur.next
pos -= 1
node.next = cur
node.pre = pre
cur.pre = node
pre.next = node
def remove(self, data):
if self.get_size() <= 0:
return
cur = self._head
pre = None
while cur:
if cur.data == data:
cur.next.pre = pre
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, data):
cur = self._head
pos = 0
while cur:
if cur.data == data:
return pos
else:
cur = cur.next
pos += 1
return -1
def r_travel(self):
cur = self._end
while cur:
print("{}".format(cur.data), end="->")
cur = cur.pre
print("null")
def travel(self):
cur = self._head
while cur:
print("{}".format(cur.data), end="->") -> None
cur = cur.next
print("null")
if __name__ == "__main__":
l = DoublelinkList()
l.append(3)
l.travel()
l.add(0)
l.add(1)
l.append(4)
l.travel()
l.r_travel()
l.insert(5, 2)
l.r_travel()
l.remove(3)
l.r_travel()
测试结果
单向循环链表
class Node():
def __init__(self, data):
self.data = data
self.next = None
class SingleCyclelinkList():
def __init__(self):
self._head = None
def add(self, data):
node = Node(data)
if self._head is None:
self._head = node
node.next = self._head
else:
node.next = self._head
cur = self._head
while cur.next is not self._head:
cur = cur.next
cur.next = node
self._head = node
def append(self, data):
node = Node(data)
cur = self._head
while cur:
if cur.next == self._head:
node.next = self._head
cur.next = node
break
else:
cur = cur.next
def get_size(self):
cnt = 0
cur = self._head
while cur:
if cur.next == self._head:
cnt += 1
break
else:
cur = cur.next
cnt += 1
return cnt
def insert(self, data, pos):
node = Node(data)
cur = self._head
pre = None
if pos <= 0:
self.add(data)
elif pos >= self.get_size():
self.append(data)
else:
while pos:
pre = cur
cur = cur.next
pos -= 1
node.next = cur
pre.next = node
def remove(self, data):
cur = self._head
pre = None
while cur:
if cur.data == data:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, data):
cur = self._head
pos = 0
while cur and cur.next is not self._head:
if cur.data == data:
return pos
else:
cur = cur.next
pos += 1
return -1
def travel(self):
cur = self._head
while cur:
if cur.next is self._head:
print("{}".format(cur.data), end="->")
break
else:
print("{}".format(cur.data), end="->")
cur = cur.next
print("null")
if __name__ == "__main__":
l = SingleCyclelinkList()
l.insert(1,0)
l.insert(2,0)
l.insert(3,4)
l.insert(3,5)
l.insert(5,2)
l.travel()
l.remove(3)
l.travel()
print(l.search(5))
测试结果
