一 简介

1 链表简介

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

---

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表，python在其标准库中没有链接列表。

2 单项链表和双向链表

1 单链表

1 示意图

2 存储结构

上图就是单向链表的存储结构原理图，由图中我们可以看出每个节点都由两部分组成，一个是data数据域，另一个是指向下一节点的next指针域，指针域不存放任何数据，然后通过这样的方式一直指下去，最后便形成了一条类似铁链的结构，所以称为链表，最后的next指针为null，说明到了最后一个节点，(python中为None),最后一个节点的指针不指向任何节点，所以next=null.

2 双向链表

1 示意图

2 存储结构

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

二 python单向链表实现

1 单项链表实现append和 iternodes

            
              #!/usr/bin/poython3.6
#conding:utf-8
class  SingleNode:
    ''' 定义一个节点'''
    def  __init__(self,value,next=None,prev=None):  #追加的下一跳就是None
        self.value=value  # 定义节点中的数据
        self.next=next   # 定义节点的指针
        self.prev=prev   # 定义节点的上一个元素
    def  __repr__(self):
        return str(self.value)  # 此处返回的是指针的值

class  LinkedList:
    '''容器类，用来存储一个个节点，链表在内存中并非是连续的，而list在内存中是连续的'''
    def __init__(self):
        self.nodes=[]  #定义存储的容器，对于一个不需要插入和删除的链表来说，使用list更方便,但插入和remove是不方便的
        self.head=None  #默认的，链表的头和尾都是空
        self.tail=None  # 追加知道tail不用从头进行处理，尾巴加上
    def append(self,val):
        node=SingleNode(val)  #此处生成一个node的值
        prev=self.tail #查看当前有多少个元素，及就是未加的节点之前，前一个节点
        if  prev  is None:  # 如果当前尾巴是None,则表明无元素。tail指的是node,此处是针对第一个元素的执行
            self.head=node #前一个的下一个是None
        else:
            prev.next = node  # 前一个元素的下一个元素指向当前的元素,若只放一个，则next是None，用默认值就可以
        self.nodes.append(node) #追加，此处需要前一个元素
        self.tail=node  # 前一个元素的下一个指向的是node，
    def  iternodes(self,reverse=False):#遍历当前元素
        current= self.head  # 遍历
        while current:
            yield current
            current=current.next

l1=LinkedList()
l1.append(10)
l1.append(11)
l1.append(12)
l1.append(20)
for i in  l1.iternodes():
    print (i)
            
          

结果如下

2 双向链表实现如下

            
              #!/usr/bin/poython3.6
#conding:utf-8
class  SignerNode:
    def __init__(self,value,next=None,prev=None):
        self.value=value
        self.next=next
        self.prev=prev
    def __repr__(self):
        return  str(self.value)

class  LinkedList:
    def __init__(self):
        self.tail = None
        self.head = None
    def append(self,val):
        node=SignerNode(val)
        if self.tail  is None:  # only one
            self.head=node
        else:
            self.tail.next=node
            node.prev=self.tail  #前一个应该指向当前的前一个
        self.tail=node  # 将自己变成尾部
    def  iternodes(self,reverse=False):
        current=self.tail  if reverse else  self.head
        while current:
            yield  current
            current=current.prev  if  reverse  else  current.next
    def  pop(self):  # 从尾部进行删除
        if self.tail  is  None:  #如果没尾部，则直接为空
            raise  Exception('Empty')
        # tail中只有一个元素，则其一定不是None,但一定需要拿到
        tail = self.tail  #当前的尾巴
        prev=tail.prev   # 获取尾巴的前一个
        # next=tail.next    # 尾巴的后一个恒定位None
        if  prev  is  None: # 此处表示其如果只有一个元素,则头部和尾部都为空
            self.head=None
            self.tail=None
        else:  # 此处不止一个元素
            self.tail=prev  #将tail指定到前面的一个
            prev.next=None # 前一个的下一个是None
        return  tail.value  # 送进来的是谁，返回的应该就是谁
    def getitem(self,index): # 此处不支持负向索引，此处时通过索引进行操作
        if index < 0 :
            return None
        current=None
        for  k,v in enumerate(self.iternodes()):
            if  index==k:
                current=v  # 如果存在，此处返回为Node
                break
        if current  is  not  None:  # 此处是判断元素的值是否是None，如果时None,则返回，查看遍历是否到头
            return  current
    def insert(self,index,value):
        if  index <0:
            raise Exception('Error')
        current = None
        for k, v in enumerate(self.iternodes()):
            if index == k:
                current = v  # 如果存在，此处返回为Node
                break
        if current  is   None:  # 此处是判断元素的值是否是None，如果时None,则返回，查看遍历是否到头,若没找到，则追加
            self.append(value)  # 此处尾部的修改是不用管的
            return
        prev = current.prev
        next = current.next
        node = SignerNode(value)
        if prev  is None:  # 若你是开头，则prev为None
            self.head=node
            node.next=current # 当前的下一个是之前的
            current.prev=node # 之前的前一个之前是None,现在由于加入了元素，因此前一个的前一个是当前的节点
        else: # 在后面的，本身最后的没动，只是他前面的在动
            node.prev=prev  # 插入的前一个是之前的
            node.next=current # 插入的后一个是当前节点
            current.prev= node   # 当前节点的之前修改成node
            prev.next=node  # 前一个的需要指向当前的
    def  remove(self,index):
        if self.tail is None:  # 此处表示是最后一个
            raise Exception('Empty')
        if index <0:
            raise ValueError('Wrong Index {}'.format(index))
        current=None
        for k, v in enumerate(self.iternodes()):
            if index == k:
                current = v  # 如果存在，此处返回为Node
                break
        if current  is None: # 没找到
            raise  ValueError('Wrong   Index {} .out of  boundary'.format(index))
        prev=current.prev
        next = current.next

        if prev  is None  and  next  is  None: # 此处表示只有一个元素 only  one的情况
            self.head=None
            self.tail=None
        elif  prev  is None:  # 则表示为开始元素
            self.head=next
            next.prev=None
        elif next is  None: # 此处表示是最后一个元素
            self.tail=prev
            prev.next=None
        else: # 不是头部，也不是尾部
            prev.next=next
            next.prev=prev
        print (current)
        del  current
l1=LinkedList()
node=SignerNode('1234')
l1.append(node)
node=SignerNode(1)
l1.insert(0,node)
node=SignerNode(2)
l1.insert(1,node)
node=SignerNode(100)
l1.insert(100,node)
for  i  in   l1.iternodes():
    print (i)
print ('#'*20)
print  (l1.pop())
print (l1.pop())
for  i  in   l1.iternodes():
    print (i)
print ('~'*20)
l1.remove(1)
print ('*'*20)
for  i  in   l1.iternodes():
    print (i)
            
          

结果如下

3 使用_ setitem_ ，_ getitem_ ,__iter__实现对链表的访问

            
              #!/usr/bin/poython3.6
#conding:utf-8
class  Node:
    def __init__(self,value,next=None,prev=None):
        self.value=value
        self.next=next
        self.prev=prev
    def __repr__(self):
        return  str(self.value)

class  NodeList:
    def __init__(self):
        # self.lst=[]
        self.tail=None
        self.head=None
    def append(self,value):
        node = Node(value)
        current=self.tail
        if current  is None:  # 此处表示无数据
            self.head=node
        else:  #此处表示有数据
            current.next=node
            node.prev=current
        self.tail=node
        # self.lst.append(node)
    def  pop(self):
        current=self.tail
        prev=current.prev
        next=current.next
        if  current  is None:
            raise  Exception('Empty')
        if  prev  is None:  # 此处是判断只有一个元素
            self.head=None
            self.tail=None
        else:
            self.tail=prev
            prev.next=None
    def  iterable(self,reverse=True):
        current=  self.head    if  reverse else  self.tail
        while current:
            yield  current
            current= current.next  if reverse  else current.prev
    def insert(self,index,value):
        if index < 0 :
            raise Exception('Index  illegal')
        node1=Node(value)
        current=None
        for  k,node  in   enumerate(self.iterable()):
            if  index==k:
                current=node
                break
        if  current  is  None:
            self.append(node1)
            return
        prev=current.prev
        mext=current.next
        if prev is None:  # 此处表示是第一个
            self.head=node1
            node1.next=current
            current.prev=node1
        else:
            node1.next=current
            node1.prev=current.prev
            prev.next=node1
            current.prev=node1
    def remove(self,index):
        if index < 0:
            raise Exception('Index  illegal')
        current = None
        for k, node in enumerate(self.iterable()):
            if index == k:
                current = node
                break
        if current  is None:
            raise Exception('Index  not exist')
        prev=current.prev
        next=current.next
        if  prev  is None  and  next  is None:
            self.tail=None
            self.head=None
        elif prev  is None:
            self.head=current.next
            next.prev=None
        elif  next is None:
            self.tail=current.prev
            prev.next=None
        else:
            prev.next=next
            next.prev=prev
    def __getitem__(self, index):
        for  i,node  in enumerate(self.iterable(True  if index >=0  else  False), 0  if  index >= 0 else 1 ): # 此处表示枚举法的起点为0
            if  ( i   if  index>=0  else  -i) == abs(index):
                return node

    def __iter__(self):
        return  iter(self.iterable())
    def __setitem__(self,index, value):
        self[index].value=value
node=Node(1)
l1=NodeList()
l1.append(node)
node=Node(2)
l1.append(node)
node=Node(3)
l1.append(node)
node=Node(4)
l1.append(node)
node=Node(5)
l1.append(node)
for i in l1.iterable():
    print (i)
print ('*'*30)
l1.pop()
l1.pop()
l1.pop()
for i in l1.iterable():
    print (i)
print ('#'*30)
l1.insert(0,100)
l1.insert(100,10)
l1.insert(2,'abc')
for i in l1.iterable():
    print (i)
print ('~'*30)
l1.remove(2)
l1.remove(1)
l1.remove(0)
l1.remove(1)
for i in l1.iterable():
    print (i)
l1.append(node)
l1.append(node)
print ('}'*20)
print (l1[0])
print (l1[1])
print ('}'*20)
for i  in l1:
    print (i)
print ('['*30)
l1[1]=4
for i  in l1:
    print (i)
l1[0]=10
print (']'*30)
for i  in l1:
    print (i)
l1[2]=20
print ('$'*30)
for i  in l1:
    print (i)
l1[2]=40
print ('('*30)
for i  in l1:
    print (i)