数组是常用的数据结构，但是有其局限性：

编译期需要确定元素大小
数组在内存中是连续的，插入或者删除需要移动数组中其他数据
数组适合处理确定长度的，对于插入或者删除不敏感的数据。如果数据是频繁变化的，就需要选择其他数据结构了。本文介绍链表。

链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表由一系列的节点组成，节点可以在运行时动态生成，因此链表的长度没有逻辑上的限制，有限制的是堆的大小。在单向链表中。每个节点包含两部分：数据域与指针域。数据域存储数据元素，指针域存储下一结点的指针。

一、单向链表

单向链表是最简单的形式，每个节点是包含两个域：信息域（元素域）和链接域。链接指向链表中的下一个节点，最后一个节点的链接域则指向一个空值。
在这里插入图片描述

head 是头指针，保存首地址，item 存储数据，next 指向下一节点地址。

链表失去了序列的随机读取优点，同时链表增加了指针域，空间开销也较大，但它对存储空间的使用要相对灵活。

1、节点定义

节点数据结构为数据元素item与指针next。

class Node(object):"""单链表的结点"""def __init__(self, item):self.item = itemself.next = None

2、链表定义

（1）定义首地址与列表创建

class SingleLinkList(object):"""单链表"""def __init__(self):self._head = None

列表创建：

    link_list = SingleLinkList()# 创建节点node1 = Node(1)node2 = Node(2)# 将节点添加到链表link_list._head = node1# 将第一个节点的next指针指向下一节点node1.next = node2# 访问链表print(link_list._head.item)  # 访问第一个节点数据print(link_list._head.next.item)  # 访问第二个节点数据

（2）链表中的操作方法

is_empty() 链表是否为空
length() 链表长度 ( o(n) )
items() 获取链表数据迭代器
add(item)链表头部添加元素 ( o(1) )
append(item) 链表尾部添加元素 ( o(1) )
insert(pos, item) 指定位置添加元素 ( o(n) )
remove(item) 删除节点 ( o(n) )
find(item) 查找元素是否存在 ( o(n) )

（3）python代码实现

class singleLinkList(object):def __init__(self, Node=None):self._head = Nodedef is_empty(self):return self._head == Nonedef length(self):cur = self._headcnt = 0while cur != None:cnt += 1cur = cur.nextreturn cntdef travel(self):cur = self._headwhile cur != None:print(cur.item, end=' ')cur = cur.nextdef add(self, val):"插入头节点"node = Node(val)node.next = self._headself._head = nodedef append(self, val):"插入尾节点"node = Node(val)if self.is_empty():self._head = nodeelse:cur = self._headwhile cur.next != None:cur = cur.next  # 到当前尾节点cur.next = nodedef insert(self, pos, val):"""在指定位置插入结点"""if pos <= 0:self.add(val)elif pos >= self.length() - 1:self.append(val)  # append 在链表尾部加节点else:node = Node(item)  # 定义节点？cnt = 1cur = self._headpre = Nonewhile cnt != pos:pre = curcur = cur.nextcnt += 1cur =  nodecur.next = pre.nextpre.next = curdef remove(self, val):"移除指定元素"if self.is_empty():print("Empty linklist, Error！")else:cur = self._headpre = Nonewhile cur.item != val:pre = curcur = cur.nextpre.next = cur.nextprint("delete successfully")del curdef search(self, val):"遍历查找某个值"cur = self._headcnt = 1while cur.item != val:cur = cur.nextcnt += 1return cnt  # 返回位置

二、双链表

双向链表在节点中增加一个指针域指向节点的前驱节点。因此每个节点有两个链接：一个指向前一个节点，而另一个链接指向下一个节点。头结点没有前驱结点、尾节点没有后驱结点(或者指向空值)。
在这里插入图片描述

1、节点定义

class Node(object):"""双向链表节点"""def __init__(self, item):# item 存放数据元素self.item = item# next 指向下一个节点self.next = None# pre 指向上一结点self.pre = None

2、双向链表python实现

class BilateralLinkList(object):"""双向链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""链表长度"""# 初始指针指向headcur = self._headcount = 0# 指针指向None 表示到达尾部while cur is not None:count += 1# 指针下移cur = cur.nextreturn countdef travel(self):"""遍历链表"""# 获取head指针cur = self._head# 循环遍历while cur is not None:# 返回生成器yield cur.item# 指针下移cur = cur.nextdef add(self, item):"""向链表头部添加元素"""node = Node(item)if self.is_empty():# 头部节点指针修改为新节点self._head = nodeelse:# 新结点指针指向原头部节点node.next = self._head# 原头节点pre指针指向新节点self._head.pre = node# head 指向新节点self._head = nodedef append(self, item):"""尾部添加元素"""node = Node(item)if self.is_empty():  # 链表无元素# 头部节点指针修改为新节点self._head = nodeelse:  # 链表有元素# 移动到尾部cur = self._headwhile cur.next is not None:cur = cur.next# 新节点上一级指针指向旧尾部node.pre = cur# 旧尾部指向新节点cur.next = nodedef insert(self, index, item):""" 指定位置插入元素"""if index <= 0:self.add(item)elif index > self.length() - 1:self.append(item)else:node = Node(item)cur = self._headfor i in range(index):cur = cur.next# 新节点的向下指针指向当前节点node.next = cur# 新节点的向上指针指向当前节点的上一节点node.pre = cur.pre# 当前上一节点的向下指针指向nodecur.pre.next = node# 当前节点的向上指针指向新结点cur.pre = nodedef remove(self, item):""" 删除结点 """if self.is_empty():returncur = self._head# 删除元素在第一个节点if cur.item == item:# 只有一个元素if cur.next is None:self._head = Nonereturn Trueelse:# head 指向下一节点self._head = cur.next# 下一节点的向上指针指向Nonecur.next.pre = Nonereturn True# 移动指针查找元素while cur.next is not None:if cur.item == item:# 上一结点向下指针指向下一结点cur.pre.next = cur.next# 下一结点向上指针指向上一结点cur.next.pre = cur.prereturn Truecur = cur.next# 删除元素在最后一个if cur.item == item:# 上一结点向下指针指向Nonecur.pre.next = Nonereturn Truedef find(self, item):"""查找元素是否存在"""return item in self.items()

常用操作：
is_empty()，判断链表是否为空，o(n)
length()，返回链表长度，o(n)
travel()，遍历链表，o(n)
add（item），在头部添加一个结点，o(1)
append(item)，在尾部添加一个结点，o(1)
insert(position,item)，在指定位置添加结点，o(n)
remove(item)，删除值为item的第一个结点，o(n)
search(item)，查找结点是否存在，o(n)

三、单向循环链表

当单向链表的尾节点不指向None，而是指向头结点的时候，那么就构成了一个单向循环链表。

单循环链表中一些操作的时间复杂度：

is_empty()，判断链表是否为空，o(n)
length()，返回链表长度，o(n)
travel()，遍历链表，o(n)
add（item），在头部添加一个结点，o(n)
append(item)，在尾部添加一个结点，o(1)
insert(position,item)，在指定位置添加结点，o(n)
remove(item)，删除值为item的第一个结点，o(n)
search(item)，查找结点是否存在，o(n)

class Node(object):"""节点"""def __init__(self, item):self.item = itemself.next = Noneclass SinCycLinkedlist(object):"""单向循环链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head == Nonedef length(self):"""返回链表的长度"""# 如果链表为空，返回长度0if self.is_empty():return 0count = 1cur = self._headwhile cur.next != self._head:count += 1cur = cur.nextreturn countdef travel(self):"""遍历链表"""if self.is_empty():returncur = self._headprint cur.item,while cur.next != self._head:cur = cur.nextprint cur.item,print ""def add(self, item):"""头部添加节点"""node = Node(item)if self.is_empty():self._head = nodenode.next = self._headelse:#添加的节点指向_headnode.next = self._head# 移到链表尾部，将尾部节点的next指向nodecur = self._headwhile cur.next != self._head:cur = cur.nextcur.next = node#_head指向添加node的self._head = nodedef append(self, item):"""尾部添加节点"""node = Node(item)if self.is_empty():self._head = nodenode.next = self._headelse:# 移到链表尾部cur = self._headwhile cur.next != self._head:cur = cur.next# 将尾节点指向nodecur.next = node# 将node指向头节点_headnode.next = self._headdef insert(self, pos, item):"""在指定位置添加节点"""if pos <= 0:self.add(item)elif pos > (self.length()-1):self.append(item)else:node = Node(item)cur = self._headcount = 0# 移动到指定位置的前一个位置while count < (pos-1):count += 1cur = cur.nextnode.next = cur.nextcur.next = nodedef remove(self, item):"""删除一个节点"""# 若链表为空，则直接返回if self.is_empty():return# 将cur指向头节点cur = self._headpre = None# 若头节点的元素就是要查找的元素itemif cur.item == item:# 如果链表不止一个节点if cur.next != self._head:# 先找到尾节点，将尾节点的next指向第二个节点while cur.next != self._head:cur = cur.next# cur指向了尾节点cur.next = self._head.nextself._head = self._head.nextelse:# 链表只有一个节点self._head = Noneelse:pre = self._head# 第一个节点不是要删除的while cur.next != self._head:# 找到了要删除的元素if cur.item == item:# 删除pre.next = cur.nextreturnelse:pre = curcur = cur.next# cur 指向尾节点if cur.item == item:# 尾部删除pre.next = cur.nextdef search(self, item):"""查找节点是否存在"""if self.is_empty():return Falsecur = self._headif cur.item == item:return Truewhile cur.next != self._head:cur = cur.nextif cur.item == item:return Truereturn False