摘要： 在C/C++语言中，常用结构体+指针来实现链表；而在Python语言中，使用类(class) 来实现链表。
一、创建节点(Node)
链表由多个节点(Node)组成，而每个节点都有两要素组成：
（1）value：该节点的值
（2）next：指向下一个节点
class Node():
def __init__(self, value):
self._value = value
self._next = None
二、创建链表(LinkedList)
创建链表时，链表只有一个参数，就是链表的头部(head)，换句话说链表只知道它的头，其余节点只能通过访问其头部来知道。
class LinkedList():
def __init__(self):
self._head = None
三、链表的基础成员函数
（1）、is_Empty(): 检查该链表是否为空，为空则返回 True，否则返回 False。
（2）、length(): 返回链表节点的数量
（3）、travel(): 遍历所有节点
class LinkedList():
def __init__(self, head=None):
self._head = head
# judge whether the linkedlist is empty
def isEmpty(self):
return self._head == None
# count the numbers of node of linkedlist
def length(self):
if self.isEmpty():
return 0
else:
cur = self._head
count = 1
while cur._next != None:
count += 1
cur = cur._next
return count
# travel all nodes
def travel(self):
if self.isEmpty():
print("The linkedlist is empty!")
else:
cur = self._head
values = []
while cur != None:
values.append(cur._value)
cur = cur._next
print(values)
四、链表的功能成员函数
（1）、add(): 头部添加节点
（2）、append(): 尾部添加节点
（3）、insert(): 插入节点
（4）、remove(): 删除等于某个值的全部节点
（5）、delete(): 删除某个索引对应的节点
（6）、searchbyvalue(): 根据值返回节点的索引
（7）、searchbyindex(): 根据索引返回节点的值
class LinkedList():
def __init__(self, head=None):
self._head = head
# judge whether the linkedlist is empty
def isEmpty(self):
return self._head == None
# count the numbers of node of linkedlist
def length(self):
if self.isEmpty():
return 0
else:
cur = self._head
count = 1
while cur._next != None:
count += 1
cur = cur._next
return count
# travel all nodes
def travel(self):
if self.isEmpty():
print("The linkedlist is empty!")
else:
cur = self._head
values = []
while cur != None:
values.append(cur._value)
cur = cur._next
print(values)
# add a node before the head of linkedlist
def add(self, value):
node = Node(value)
node._next = self._head
self._head = node
# add a node in the tail of linkedlist
def append(self, value):
node = Node(value)
if self.isEmpty():
self._head = node
else:
cur = self._head
while cur._next != None:
cur = cur._next
cur._next = node
# insert a node in the position of linkedlist
def insert(self, pos, value):
if pos <= 0:
self.add(value)
elif pos > (self.length()-1):
self.append(value)
else:
node = Node(value)
cur = self._head
index = 0
while index < (pos-1):
index += 1
cur = cur._next
node._next = cur._next
cur._next = node
# remove all nodes whose value is equal to the input value
def remove(self, value):
pre = None
cur = self._head
while cur != None:
if cur._value == value:
if pre == None:
self._head = self._head._next
cur = self._head
continue
else:
pre._next = cur._next
cur = cur._next
continue
pre, cur = cur, cur._next
# delete a node from linkedlist according to its index
def delete(self, index):
if index < 0 or index > (self.length()-1):
print("The input index is out of range!")
elif index == 0:
self._head = self._head._next
else:
count = 1
pre, cur = self._head, self._head._next
while count<index:
count += 1
pre, cur = cur, cur._next
pre._next = cur._next
# search index of node according to the value, if not this value, return False
def searchbyvalue(self, value):
count = 0
cur = self._head
index = []
while cur != None:
if cur._value == value:
index.append(count)
count += 1
cur = cur._next
if not index:
return False
else:
return index
# search the value of node according to the index
def searchbyindex(self, index):
count = 0
cur = self._head
if index < 0 or index > (self.length()-1):
print("The input index is out of range")
else:
while count < index:
count += 1
cur = cur._next
return cur._value
