单向双向链表的实现

用面向对象实现LinkedList链表

单向链表实现append、iternodes方法

双向链表实现append、pop、insert、remove、iternodes方法

链表的好处：

            查询慢、插入追加删除快

思路：

# 单向链表 1 2 2 3 3 4 4 5 5 6 None 最基本的链表结构

# 链表由 每一个数据块组成 串联在一起就是链表

#先定义数据块 Node

class Node1:  ##(item -> next)

    def __init__(self,item, next=None):

        self.item = item

        self.next = next

    def __repr__(self):

        return '<{}--->{}>'.format(self.item,

                                      self.next.item if self.next else 'None') #？？？怎么理解这句话 

#构造单向链表

class Singelinked:

    def __init__(self): #设定开头和结尾 这是一个链表最基本的属性 初始链表的开头和结尾为None

        self.head = None

        self.tail = None

    def append(self,item):

        Node = Node1(item)  ##构造一个要添加的节点 然后写入到链表中

        if self.head is None:  #

            self.head = Node ##如果是空的直接追加

            self.tail = Node     

        else:

            self.tail.next = Node #不为空 就在最后一个尾部 追加 然后追加完成后 把前一个的next 变成 node

            self.tail = Node

        return self

    def iterlink(self):

        current = self.head   #当前的头部

        while current:      #无限循环 知道 当前为None 等效False

            yield current

            current = current.next  

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

##先定义数据块 Node

class Node2:  ##(item -> next)

    def __init__(self,item, next= None,prev=None): ##双向链表除了头和尾之外都是双向的

        self.prev = prev

        self.item = item

        self.next = next

    def __repr__(self):

        return '<{}<--{}-->{}>'.format(self.prev.item if self.prev else 'None',self.item,self.next.item if self.next else 'None')

#构造双向链表

class DubleLineked:

    def __init__(self):

        self.head = None

        self.tail = None

        self.size = None

    def append(self,item):

        Node = Node2(item)  ##构造一个要添加的节点 然后写入到链表中

        if self.head is None:

            self.head = Node ##如果是空的直接追加

            #self.tail = Node

        else:

            Node.prev = self.tail

            self.tail.next = Node

        self.tail = Node

        return self

    def insert(self,index,value):

        if index <0 : #只接受正索引

            raise IndexError('Negative index err{}'.format(index))

        current = None

        for i,node in enumerate(self.iterlink()):

            if i == index:

                current = node

                break

        else:

            self.append(value)

            return  ########################## if使用后记得用return 终止函数执行

        ##创建一个待加入节点对象； 如果是空 或者超界的情况 则直接执行append语句 append有包装的语句

        node = Node2(value) #包装成模块

        prev = current.prev

        # next = current.next

        ## 放在头 考虑修正关系  切记 修改后要修改头部 为不加入不用考虑 因为append 就是尾部和空的加入

        if index == 0 : # 除了空和尾部追加 就是 头部 和中部了 分开讨论一下就ok了 i==0 or prev = None

            current.prev = node

            node.next = current

            self.head = node

        else:#中部追加

            node.prev = prev

            node.next = current

            current.prev = node

            prev.next = node

        return

    def pop(self): #尾部移除

        if self.tail is None: #考虑空链表

            raise Exception('{}'.format(None))

        else:

            node = self.tail #取模块

            item = node.item # item 是模块内的data

            prev = node.prev #模块的前一项

            if prev is None and next is None: #只有一个node

                self.head = None

                self.tail = None

                return item  #返回一个数值

            else:##两个元素移除尾部 最后剩下一个

                self.tail = prev ##node.prev

                prev.next = None

                return item   #返回一个数值

    def remove(self,index): #任意位置移除 比较index

        if index <0 :

            raise IndexError("Do not support nagative index {}".format(index))

        if self.head is None or self.tail is None:

            raise Exception('Empty')

        for i,node in enumerate(self.iterlink()):

            if i == index:

                current = node

                break

        else: ##超出索引范围 移除最后一个

            self.pop() #抛出最后一个

            return  ##记得终止函数执行@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

            #raise IndexError('超出索引边界')     两个都可以

        ###break 说明找到了要索引的值 这时候就要对这个值进行操作了

        prev = current.prev

        next = current.next

        item = current.item

        #分4情况

        #就一个模块 既是头 有事尾

        #在开头

        #在结尾

        #在中间

        if prev is None and next is None: #JUEST 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

    def iterlink(self,reversed = False): #双向迭代就是翻转的问题 想sorted函数

        current = self.head if not reversed else self.tail

        while current:

            yield current

            current = current.next if not reversed else current.prev

#输出结果测试

a = DubleLineked()

a.append(1)

a.append(2)

a.append(3)

a.insert(100,'abd')

a.insert(0,112)

a.insert(3,'liajibin')

a.pop()

print(a.pop())

a.remove(1)

for x in a.iterlink():

    print(x)