链表：链表是一种非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于栈和队列，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
**
链表图示.png
python代码实现如下：
# coding:utf-8
class Node(object):
def __init__(self, val):
self.val=val #节点值
self.next = None #指向下一个节点
class SignalLink(object):
"""
单链表：每个节点包含连个域，一个信息域和一个链接域，链接域指向下一个节点，最后一个链接域指向空值
"""
def __init__(self, node=None):
self._head = node#指定首节点
def is_empty(self):
"""
判断链表为空
"""
return self._head==None
def length(self):
"""
链表长度
"""
count = 0
cur = self._head
while cur:
count += 1
cur = cur.next
return count
def travel(self):
"""
遍历链表
"""
cur = self._head
while cur:
print(cur.val)
cur = cur.next
def add(self, val):
"""
链表头部添加元素
"""
node = Node(val)
node.next = self._head
self._head = node
def append(self, val):
"""
链表尾部添加元素
"""
node = Node(val)
if self.is_empty():#空
self._head = node
else:
cur = self._head
while cur.next:#有下一个元素
cur = cur.next #遍历到最后一个元素
cur.next = node
def insert(self, idx, item):
"""
在指定位置添加元素（在第二个位置插入，即索引为1）
"""
cur = self._head
index = 0
if idx <= 0:
self.add(item)
elif idx >= (self.length()-1):
self.append(item)
else:
pre = self._head
index = 0
while index < (idx-1):#碰到执行索引退出循环
index += 1
pre = pre.next
node = Node(item)
node.next = pre.next
pre.next = node
def delete(self, item):
"""
删除节点
"""
cur = self._head
pre = None
while cur:
if cur.val == 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:
if cur.val == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
sl = SignalLink()
sl.append(1)
sl.append(2)
sl.append(3)
print(sl.length())
sl.travel()
print(sl.search(1))
print(sl.search(5))
sl.delete(3)
sl.travel()
print(sl.insert(1,100))
sl.travel()
