什么是链表

顺序表的储存分为一体式结构和分离式结构，但总的来说存储数据的内存是一块连续的单元，每次申请前都要预估所需要的内存空间大小。这样就不能随意的增加我们需要的数据了。链接就是为了解决这个问题。它的数据存储方式是每插入一个数据，就在内存中申请一块存储空间来保存，那么新增加的数据如何和之前的数据保持关联呢？解决方法就是在原来的数据内存里保存新增加的数据的内存地址，这样就相当于用“一根线”把它们都串了起来，因此每次新插入一个数据，就要在内存中申请两个连续的空间，一个用来储存数据，一个用来储存下一个数据的地址。寻址方式就是从第一个数据开始依次往下寻找。

(ps:图画的有点丑2333)

另外，链表和顺序表统称为线性表。

同时，我们需要一个内存空间，用来保存链表第一个数据的地址，因此，完整的结构应该是

了解是链表的概念后，我们就要想办法来实现它，那么，用什么方式实现呢？

我们知道，链表的实现需要把数据以及所支持的结构放到一起形成一个整体，这样才构成链表。这时就要用到面向对象中类的概念了。但因为链表其中还保存数据地址这个功能，我们就先要来学习先python中有关变量地址的一点知识。

首先，我们知道，在其他语言，类似C语言中，表示地址用的是指针，但在python中根本没有指针这个类型，那我们要如何操作跟地址有关的概念呢？其实，python中定义变量和C语言是不一样的，在C语言中定义一个变量前需要声明变量的类型，例如：int c = 1。这样就相当于在内存中划出一块地方用来存放整数1。但在python中，为什么我们可以不用声明变量的类型就可以定义变量了呢？这是因为我们定义的那个变量保存的不是我们想要赋予变量的值，而是存放该值的内存地址，举个例子，如图：

定义a = 10  b = 20，那么在内存中的存储方式为

当进行交换后，a, b = b, a，此时：

因此保存变量的的那块内存中的值根本没有变化，变化的是a和b中所指向的内存地址。

把这种思想用到我们要实现的类中来，也就是类中存在两个内存，一个存放数据，一个存放下个节点的地址。当实例化一个对象后，elem保存数据的值，而next保存下一个对象的地址。如图：

代码实现

#coding:utf-8

classSingleNode(object):"""单链表的结点"""

def __init__(self,elem):#_item存放数据元素

self.elem =elem#_next是下一个节点的标识

self.next =NoneclassSingleLinkList(object):"""单链表"""

def __init__(self, node=None):

self.__head =nodedefis_empty(self):"""判断链表是否为空"""

return self.__head ==Nonedeflength(self):"""链表长度"""

#cur初始时指向头节点

cur = self.__headcount=0#尾节点指向None，当未到达尾部时

while cur !=None:

count+= 1

#将cur后移一个节点

cur =cur.nextreturncountdeftravel(self):"""遍历链表"""cur= self.__head

while cur !=None:print(cur.elem, end=" ")

cur=cur.nextdefadd(self, elem):"""头部添加元素"""

#先创建一个保存item值的节点

node =SingleNode(elem)#将新节点的链接域next指向头节点，即__head指向的位置

node.next = self.__head

#将链表的头_head指向新节点

self.__head =nodedefappend(self, elem):"""尾部添加元素"""node=SingleNode(elem)#先判断链表是否为空，若是空链表，则将__head指向新节点

ifself.is_empty():

self.__head =node#若不为空，则找到尾部，将尾节点的next指向新节点

else:

cur= self.__head

while cur.next !=None:

cur=cur.next

cur.next=nodedefinsert(self, pos, elem):"""指定位置添加元素"""

#若指定位置pos为第一个元素之前，则执行头部插入

if pos <=0:

self.add(elem)#若指定位置超过链表尾部，则执行尾部插入

elif pos > (self.length() - 1):

self.append(elem)#找到指定位置

else:

node=SingleNode(elem)

count=0#pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置

pre = self.__head

while count < (pos - 1):

count+= 1pre=pre.next#先将新节点node的next指向插入位置的节点

node.next =pre.next#将插入位置的前一个节点的next指向新节点

pre.next =nodedefremove(self, elem):"""删除节点"""cur= self.__headpre=Nonewhile cur !=None:#找到了指定元素

if cur.elem ==elem:#如果第一个就是删除的节点

if cur== self.__head:#将头指针指向头节点的后一个节点

self.__head =cur.nextelse:#将删除位置前一个节点的next指向删除位置的后一个节点

pre.next =cur.nextbreak

else:#继续按链表后移节点

pre =cur

cur=cur.nextdefsearch(self, elem):"""链表查找节点是否存在，并返回True或者False"""cur= self.__head

while cur !=None:if cur.elem ==elem:returnTrue

cur=cur.nextreturnFalse#测试

if __name__ == "__main__":

ll=SingleLinkList()

ll.add(1)

ll.add(2)

ll.append(3)

ll.insert(2, 4)print("length:",ll.length())

ll.travel()print(ll.search(3))print(ll.search(5))

ll.remove(1)print("length:",ll.length())

ll.travel()

双向链表

#coding:utf-8

classNode(object):"""节点"""

def __init__(self, elem):

self.elem=elem

self.prev=None

self.next=NoneclassDoubleLinkList(object):"""单链表"""

def __init__(self, node=None):

self.__head =nodedefis_empty(self):"""判断链表是否为空"""

return self.__head ==Nonedeflength(self):"""链表长度"""

#cur初始时指向头节点

cur = self.__headcount=0#尾节点指向None，当未到达尾部时

while cur !=None:

count+= 1

#将cur后移一个节点

cur =cur.nextreturncountdeftravel(self):"""遍历链表"""cur= self.__head

while cur !=None:print(cur.elem, end=" ")

cur=cur.nextdefadd(self, elem):"""头部添加元素"""

#先创建一个保存item值的节点

node =Node(elem)#将新节点的链接域next指向头节点，即__head指向的位置

node.next = self.__head

#将链表的头_head指向新节点

self.__head =node

self.__head.prev =nodedefappend(self, elem):"""尾部添加元素"""node=Node(elem)#先判断链表是否为空，若是空链表，则将__head指向新节点

ifself.is_empty():

self.__head =node#若不为空，则找到尾部，将尾节点的next指向新节点

else:

cur= self.__head

while cur.next !=None:

cur=cur.next

cur.next=node

node.prev=curdefinsert(self, pos, elem):"""指定位置添加元素"""

#若指定位置pos为第一个元素之前，则执行头部插入

if pos <=0:

self.add(elem)#若指定位置超过链表尾部，则执行尾部插入

elif pos > (self.length() - 1):

self.append(elem)#找到指定位置

else:

cur= self.__headcount=0while count

count+= 1cur=cur.next

node=Node(elem)

node.next=cur

node.prev=cur.prev

cur.prev.next= node #cur.prev = node

cur.prev = node #cur.prev.next = node

defremove(self, elem):"""删除节点"""cur= self.__head

while cur !=None:#找到了指定元素

if cur.elem ==elem:#如果第一个就是删除的节点

if cur == self.__head:#将头指针指向头节点的后一个节点

self.__head =cur.nextif cur.next: #判断链表是不是只有一个结点

cur.next.prev =Noneelse:#将删除位置前一个节点的next指向删除位置的后一个节点

cur.prev.next =cur.nextif cur.next: #判断该结点是不是链表最后一个

cur.next.prev =cur.prevbreak

else:#继续按链表后移节点

cur =cur.nextdefsearch(self, elem):"""链表查找节点是否存在，并返回True或者False"""cur= self.__head

while cur !=None:if cur.elem ==elem:returnTrue

cur=cur.nextreturnFalse#测试

if __name__ == "__main__":

d=DoubleLinkList()

d.add(1)

d.add(2)

d.append(3)

d.insert(2, 4)print("length:",d.length())

d.travel()print(d.search(3))print(d.search(5))

d.remove(2)print("length:",d.length())

d.travel()