1.链表概念
链表是一种动态的数据结构，具体是指一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。链表的数据结构如下图所示。
链表结构
跟数组比较，链表的优势是分配内存空间的灵活性，数组的内存却是一块连续的内存。
根据链表结构不同，链表又可以分为单链表、双向链表和循环链表。
2.单链表基本操作
首先定义节点类用于存储数据和构造链表结构。
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
- 判断链表是否为空
def isEmpty(self):
return self._head == None
- 获取链表长度
需要设置计数器和一个循环遍历链表。
def getlength(self):
cur = self._head
count = 0
while cur:
count += 1
cur = cur.next
return count
- 遍历链表
def bianli(self):
cur = self._head
while cur:
print(cur.value, '')
cur = cur.next
print('\n')
- 头部插入数据
设置一个新节点指向原节点。
def add(self, elem):
cur = Node(elem)
cur.next = self._head
self._head = cur
- 尾部插入数据
def append(self, elem):
if self._head is None:
self._head = Node(elem)
else:
cur = self._head
while cur.next:
cur = cur.next
cur.next = Node(elem)
- 任意位置插入数据
注意区分头部尾部和其他位置
def insert(self, pos, elem):
if pos <= 0:
self.add(elem)
elif pos >= self.getlength():
self.append(elem)
else:
count = 0
cur = self._head
while count < pos - 1:
cur = cur.next
count += 1
node = Node(elem)
node.next = cur.next
cur.next = node
- 删除数据
删除数据要注意头部节点和尾部节点的处理，有时候会跳过这两个节点，需要认真考虑。
1）根据索引删除数据
此处有一个bug，就是头部删除的时候，明明通过cur将节点指向第二个节点，但实际运行并未起作用，只能改用其他方法。
def remove1(self, pos):
if pos < 0 or pos > self.getlength() - 1:
print('index out of range')
elif pos == 0:
self._head = self._head.next
# cur = cur
# print(cur.value)
# print('*'*10)
else:
cur = self._head
count = 0
while count < pos - 1:
cur = cur.next
count += 1
cur.next = cur.next.next
2）根据元素删除数据
此处有两种思路，第一种思路比较直，是判断next是不是等于要删除元素值，如果是就指向next的next，这个要注意尾部元素没有next，涉及next为None报错的问题，需要特别处理。
第二种思路很巧妙，设置一个前向节点，前向节点记录当前元素之前的值，遇到要删除的元素的时候，直接跳过该节点指向下一个节点。
#思路1：
def remove_elem(self, elem):
cur = self._head
if not cur:
return None
if cur.value == elem:
self._head = cur.next
while cur.next:
if cur.next.value == elem:
cur.next = cur.next.next
else:
cur.next = cur.next
if cur.next is None:
break
else:
cur = cur.next
#思路2：
def remove(self, elem):
cur = self._head
pre = None
while cur:
if cur.value == elem:
if cur == self._head:
self._head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
- 查找数据
def findelem(self, elem):
cur = self._head
count = 0
while cur:
count += 1
if cur.value == elem:
return print('%d is in the %d of chain' % (elem, count - 1))
cur = cur.next
return print('%d is not in the chain' % elem)
接下来还有双向链表和循环链表的分析，待补充。
