链表属于常见的一种线性结构，对于插入和移除而言，时间复杂度都为 O(1)
但是对于搜索操作而言，不管从链表的头部还是尾部，都需要遍历 O(n)，所以最好复杂度为 O(1)，最坏的情况就是从头部遍历到尾部才搜索出对应的元素，所以最坏复杂度为 O(n)，平均复杂度为 O(n)。
归纳如下：
* 最好复杂度为 O(1)
* 最坏复杂度为 O(n)
* 平均复杂度为 O(n)
双向链表（Double_linked_list）也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。双链表具体实现代码：
class Node(object):
#双向链表节点
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList(object):
#双向链表
def __init__(self):
self._head = None
def is_empty(self):
#判断链表是否为空
return self._head == None
def get_length(self):
#返回链表的长度
cur = self._head
count = 0
while cur != None:
count = count+1
cur = cur.next
return count
def travel(self):
#遍历链表
cur = self._head
while cur != None:
print(cur.item)
cur = cur.next
print("")
def add(self, item):
#头部插入元素
node = Node(item)
if self.is_empty():
#如果是空链表 将_head指向node
self._head = node
else:
#将node的next指向_head的头节点
node.next = self._head
#将_head的头节点的prev指向node
self._head.prev = node
#将_head指向node
self._head = node
def append(self, item):
#尾部插入元素
node = Node(item)
if self.is_empty():
#如果是空链表将_head指向node
self._head = node
else:
#移动到链表尾部
cur = self._head
while cur.next != None:
cur = cur.next
#将尾节点cur的next指向node
cur.next = node
#将node的prev指向cur
node.prev = cur
def search(self, item):
#查找元素是否存在
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
def insert(self, pos, item):
#在指定位置添加节点
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
#移动到指定位置的前一个位置
while count < (pos - 1):
count += 1
cur = cur.next
#将node的prev指向cur
node.prev = cur
#将node的next指向cur的下一个节点
node.next = cur.next
#将cur的下一个节点的prev指向node
cur.next.prev = node
#将cur的next指向node
cur.next = node
def remove(self, item):
#删除元素
if self.is_empty():
return
else:
cur = self._head
if cur.item == item:
#如果首节点的元素即是要删除的元素
if cur.next == None:
#如果链接只有这一个节点
self._head = None
else:
#将第二个节点的prev设置为None
cur.next.prev = None
#将_head指向第二个节点
self._head = cur.next
return
while cur != None:
if cur.item == item:
#将cur的前一个节点的next指向cur的后一个节点
cur.prev.next = cur.next
#将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
举个列子，交换单链表里两个链点
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Linkedlist:
def __init__(self):
self.head = None
def print_list(self):
print("linked_list:")
temp = self.head
new_list = []
while temp is not None:
new_list.append(temp.data)
temp = temp.next
print(new_list)
def insert(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def swapNodes(self, d1, d2):
prevD1 = None
prevD2 = None
if d1 == d2:
return
else:
D1 = self.head
while D1 is not None and D1.data != d1:
prevD1 = D1
D1 = D1.next
D2 = self.head
while D2 is not None and D2.data != d2:
prevD2 = D2
D2 = D2.next
if D1 is None and D2 is not None:
return
if prevD1 is not None:
prevD1.next = D2
else:
self.head = D2
if prevD2 is not None:
prevD2.next = D1
else:
self.head = D1
temp = D1.next
D1.next = D2.next
D2.next = temp
if __name__ == \'__main__\':
list = Linkedlist()
list.insert(5)
list.insert(4)
list.insert(3)
list.insert(2)
list.insert(1)
list.print_list()
list.swapNodes(1, 4)
print("After swampping")
list.print_list()
#输出
linked_list:
[1, 2, 3, 4, 5]
After swampping
linked_list:
[4, 2, 3, 1, 5]
=~休息十分钟 再继续吧~=
队列
队列 (queue) 是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列符合先进先出[FIFO]的原则。因为要排队的第一个项目，最终将是第一个要出列的项目，如在现实生活中的队列，先来的站在队列前面，后来的就只能站在队列后面啦。
队列有两种实现形式，分为两种：数组和链表。
class Node(object):
def __init__(self, elem, next = None):
self.elem = elem #表示对应的元素值
self.next = next #表示下一个链接的链点
#创建Queue类 以链表形式的队列并初始化对应的内参
class Queue(object):
def __init__(self):
self.head = None #头部链点为None
self.rear = None #尾部链点为None
#添加is_empty函数 判断队列是否为空
def is_empty(self):
return self.head is None #判断队列是否为空
#添加enqueue(elem)函数 往队列中添加一个elem元素
def enqueue(self, elem):
p = Node(elem) #初始化一个新的点
if self.is_empty():
self.head = p #队列头部为新的链点
self.rear = p #队列尾部为新的链点
else:
self.rear.next = p #队列尾部的后继是这个新的点
self.rear = p #让队列尾部指针指向这个新的点
#添加dequeue函数 从队列头部删除一个元素
def dequeue(self):
if self.is_empty():
print("empty") #队列为空则退出dequeue操作
else:
result = self.head.elem #result为队列头部元素
self.head = self.head.next #改变队列头部指针位置
return result
#peek() 查看队列头部的元素
def peek(self):
if self.is_empty():
print("NOT_FOUND")
else:
return self.head.elem
#打印出队列的所有元素
def print_queue(self):
print("queue")
temp = self.head
myqueue = [] #暂存队列数据
while temp is not None:
myqueue.append(temp.elem)
temp = temp.next
print(myqueue)
class Queue():
def __init__(self):
self.entries = [] #表示队列内的参数
self.length = 0 #表示队列的长度
self.front = 0 #表示队列头部位置
def enqueue(self, item):
self.entries.append(item) #往队列里加元素
self.length = self.length + 1 #队列长度增1
def dequeue(self):
self.length = self.length - 1
dequeued = self.entries[self.front] #dequeued是队首元素
self.front -= 1 #队首位置减少1
self.entries = self.entries[self.front:] #队列元素更新为退队之后的队列
return dequeued
def peek(self):
return self.entries[0] #直接返回队列的队首元素
复杂度分析
队列属于常见的一种线性结构，对于出队和进队而言，时间复杂度都为 O(1)
树
