链表的构造：
class Node():
'''节点'''
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):
"""判断链表是否为空"""
pass
def length(self):
"""返回链表的长度"""
pass
def travel(self):
"""遍历链表"""
pass
def add(self, item):
"""头部添加节点"""
pass
def append(self, item):
"""尾部添加节点"""
pass
def insert(self, pos, item):
"""在指定位置添加节点"""
pass
def remove(self, item):
"""删除一个节点"""
pass
def search(self, item):
"""查找节点是否存在"""
pass
single_obj = SingleLinkList()
single_obj.travel()
关于这一点，也可以写成：
def __init__(self,node):
#内部私有函数，链表头的初始化，可以直接建立空链表
self.__head = None
node = Node(100)
single_obj = SingleLinkList(node)
这样也可以就是不太高级。
-
我们先来看看如何实现第一个探空的功能，即判读链表是否为空：
这么写应该不难理解，链表为空那么__head的指向就为空，利用一下罗即判读，如self.__head ==None则返回True,代表链表为空，else链表不为空。
-
实现第二个功能，判断链表的长度即length()：
我们先模拟几个节点，并建立游标cur：
之所以不采用cur.next == None，是考虑到第三个节点也就是300节点处的cur.next == None,这样一来，记录节点数目的时候就会少一个，cur = cur.next就可以移动游标了。 同时我们还要考虑特殊情况，当这个链表为空链表的时候我们的程序能否实现要求，当链表为空，即self.__head==None，cur == None，count = 0，符合我们的预期要求。 -
实现第三个功能，遍历链表（travel）:
基本上和判断链表长度一样，进入循环打印出来即可，同样不能采用cur.next == None，否则会丢掉最后一个节点。
-
实现第四个功能，尾部添加节点，也就是append()功能：比如我们要在尾部添加400这个节点，就是要将300节点的next指向400节点。我们先建立一个node节点，移动游标cur，移动到cur.next = None，然后将cur所在的节点的next指向我们先建立的node节点即可。这时我们还需要考虑特殊情况，即空链表的情况向下如何实现我们的操作：self.__head已经指向None了怎么还能有next呢，那么我们就要针对性的改一下。我们这样更改是不是可以；但利用之前探空的功能岂不是更好。这样一来代码读起来会更流畅。
class Node():
'''节点'''
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游标，用来移动遍历节点
#count，用来记录节点数量
count = 0
cur = self.__head
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
def add(self, item):
"""头部添加节点"""
pass
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):
"""在指定位置添加节点"""
pass
def remove(self, item):
"""删除一个节点"""
pass
def search(self, item):
"""查找节点是否存在"""
pass
if __name__ == '__main__':
li = SingleLinkList()
print(li.is_empty())
print(li.length())
li.append(1)
li.append(2)
print(li.is_empty())
print(li.length())
li.append(3)
li.append(4)
li.travel()
测试结果：
True
0
False
2
1 2 3 4
-
实现第五个功能，即像链表头部添加元素（add）：假如400节点是我们即将插入的新元素，那么怎么更改指向才能实现呢？这样的指向是不是我们想要的结果呢？这样一来就很简单了。考虑一下特殊情况，如果一上来这个链表就是一个空链表呢？那么node.next = self.__head指向的就是None，因为self.__head在空链表中指向None，self.__head 指向node是没有问题的，测试结果表明一切也OK。
- 实现第六个功能，任意位置插入（insert）：
比如insert(2,400)如图所示：要想实现这个操作要如何更改程序呢？
为了方便大家理解，我们把移动到指定位置的前一个元素的游标叫做pre不再是叫做cur我们要在第二个位置插入400，是不是就要在第一个位置上开始改变指向呢？
def insert(self, pos, item):
"""在指定位置添加节点"""
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
node = Node(item)
node.next = pre.next
pre.next = node
这么写是不是很OK，但是还需要考虑特殊情况，如果用户输入的pos =< 0怎么办，我们只能默认是0，故采用头插法。如果大于等于链表的总长度，那就是尾插法了。
def insert(self, pos, item):
"""在指定位置添加节点"""
pre = self.__head
count = 0
if pos <= 0:
self.add(item)
elif pos >= (self.length()-1):
self.append(item)
else:
while count < (pos-1):
count += 1
pre = pre.next
node = Node(item)
node.next = pre.next
pre.next = node
-
实现第七个功能，实现查找（research）功能：比如我们要查找这个400节点是否在链表内，我们需要移动游标遍历每一个节点，然后一个个的去比对，等于我们的item就返回真，不等于我们的item就返回假。但是还需要考虑特殊情况，也就是当节点为空节点的时候如何处理呢？
空节点代表cur = self.__head = None，就不用执行while循环而是直接跳到return Flase，这样一来也符合功能的需求，测试结果也不存在问题。 -
实现第八个功能，即实现删除（remove）功能：
比如我们需要删除400这个节点元素，删除的方法就是讲400节点的前一个节点的next指向400节点的后一个300节点，这样一来就有两个实现方法。
- 建立两个游标，一个pre，一个cur，pre游标指向400节点之前的20节点，cur游标指向要删除的400节点，pre.next = cur.next
- 建立一个游标，实现同1相同的功能，pre游标指向要删除的400节点之前的20节点，pre.next = pre.next.next
法二我可以理解，那么我就说说法一吧，如果我们要删除的元素正好在中间：考虑在两头和空链表的特殊情况如何处理：这样是不是没问题
空链表
意味着cur = self.__head = None，程序不执行while循环，不执行任何操作，这个是没有问题的。
删除开头的节点我们还要考虑一种特殊情况，就是这个链表只有一个节点怎么办，也就是cur.next = None，删除后正好self.__head = None，我们的程序可以实现这个特殊情况。
删除结尾的节点我们理解一下，如果删除的是最后一个尾节点300，就是讲指向400的pre游标指向位于300节点的cur游标所指向的None，恰好可以完美实现，那么我们的代码就不存在问题。测试一切正常
完整代码如下：
class Node():
'''节点'''
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游标，用来移动遍历节点
#count，用来记录节点数量
count = 0
cur = self.__head
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
def add(self, item):
"""头部添加节点"""
node = Node(item)
node.next = self.__head
self.__head = node
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):
"""在指定位置添加节点"""
pre = self.__head
count = 0
if pos <= 0:
self.add(item)
elif pos >= (self.length()-1):
self.append(item)
else:
while count < (pos-1):
count += 1
pre = pre.next
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""删除一个节点"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
#先判断是否为头节点，然后再去处理头节点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
if __name__ == '__main__':
li = SingleLinkList()
print(li.is_empty())
print(li.length())
li.append(1)
li.append(2)
print(li.is_empty())
print(li.length())
li.append(3)
li.append(4)
li.add(10)
li.add(20)
li.insert(2,30)
li.insert(10,1000)
li.insert(0,999)
li.travel()
print()
print(li.search(20))
print(li.search(123))
li.travel()
li.remove(999)
li.travel()
li.remove(1000)
li.travel()
li.remove(30)
li.travel()
