目录

一、链表是什么？

二、单向链表

三、双向链表

一、链表是什么？

 1.定义：链表（Linked list）是一种常见的基础数据结构，是一种线性表，在每一个节点（数据存储单元）里存放下一个节点的位置信息

2.优点：顺序表的构建需要预知数据大小来申请连续存储空间，扩充时需要进行数据迁移，使用不灵活，链表充分利用计算机内存空间，实现灵活内存动态管理

二、单向链表

1.定义：单向链表（单链表）是链表中最简单一种形式，它的每个节点包含两个域——信息域（元素域）和链接域

(1)表元素域elem用来存放具体的数据

(2)链接域next用来存放下一个节点的位置

(3)变量p指向链表的头节点(首节点)的位置，从p出发能找到表中的任意节

2.链表相关方法：

#定义节点
class Node(object):
    def __init__(self,elem):
        self.elem=elem
        self.next=None
#构造单向链表
class SingleLinkedList:
    #判断链表是否为空：_head指向None，则为空
    def is_empty(self):
        '''
        if self._head==None:
            print("True")
        else:
            print("False")
            '''
        return self._head==None
    #单向链表初始化
    def __init__(self,node=None):
        #判断node是否为空
        if node!=None:
            headNode=Node(node)
            self._head=headNode
        else:
            self._head=node
    #计算链表长度
    def length(self):
        count=0
        curNode=self._head
        while curNode!=None:
            count+=1
            curNode=curNode.next
            return count
    #遍历链表
    def travel(self):
        curNode=self._head
        while curNode!=None:
            print(curNode.elem,end='\t')
            curNode=curNode.next
        print("  ")
    #在头部添加元素
    def add(self,item):
        #将传入的值构造成节点
        node=Node(item)
        #将新节点的链接域next指向头节点
        node.next=self._head
        #将链表的头_head指向新节点
        self._head=node
    #在尾部添加元素
    def append(self,item):
        #将传入的值构造成节点
        node=Node(item)
        if self.is_empty(): #单链表为空
            self._head=node
        else: #单链表不为空
            curNode=self._head
            while curNode.next!=None:
                curNode=curNode.next
            #修改节点，最后一个节点的next指向node
            curNode.next=node

    #在指定位置添加元素
    def insert(self,pos,item):
        #如果pos<=0，默认插入到头部
        if pos<=0:
            self.add(item)
        #如果pos>链表长度，直接在尾部追加
        elif pos>(self.length()-1):
            self.append(item)
        else:
            #构造节点
            node=Node(item)
            count=0
            preNode=self._head
            while count<(pos-1): #查找前一个节点
                count+=1
                preNode=preNode.next
            #修改指向
            #将前一个节点的next指向插入节点
            node.next=preNode.next
            #将插入位置的前一个节点next指向新节点
            preNode.next=node

    #查找节点是否存在
    def search(self,item):
        curNode=self._head
        while curNode!=None:
            if curNode.elem==item:
                return True
            curNode=curNode.next
        return False
    #删除节点
    def remove(self,item):
        curNode=self._head
        preNode=None
        while curNode!=None:
            if curNode.elem==item:
                #判断是否是头节点
                if preNode==None:#是头节点
                    self._head=curNode.next
                else:
                    #删除
                    preNode.next=curNode.next
            break
        else:
                preNode=curNode
                curNode=curNode.next
if __name__=="__main__":
    #初始化元素值为10单向链表
    singleLinkedList=SingleLinkedList(30)
    print("是否为空链表：",singleLinkedList.is_empty())
    print("链表长度为：",singleLinkedList.length())
    print("----遍历链表----")
    singleLinkedList.travel()
    print("-----查找-----",singleLinkedList.search(30))
    print("-----头部插入-----")
    singleLinkedList.add(1)
    singleLinkedList.add(2)
    singleLinkedList.add(3)
    singleLinkedList.travel()
    print("-----尾部追加-----")
    singleLinkedList.append(10)
    singleLinkedList.append(20)
    singleLinkedList.travel()
    print("-----链表长度-----",singleLinkedList.length())
    print("-----指定位置插入-----")
    singleLinkedList.insert(-1,100)
    singleLinkedList.travel()
    print("-----删除节点-----")
    singleLinkedList.remove(100)
    singleLinkedList.travel()

是否为空链表： False
链表长度为： 1
—-遍历链表—-
30      
—–查找—– True
—–头部插入—–
3    2    1    30      
—–尾部追加—–
3    2    1    30    10    20      
—–链表长度—– 1
—–指定位置插入—–
100    3    2    1    30    10    20      
—–删除节点—–
3    2    1    30    10    20     

三、双向链表

1.双向链表（双面链表）是一种更复杂的链表。每个节点有两个链接:一个指向前一个节点，当此节点为第一个节点时，指向空值，而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

2.双向链表的实现：

class Node:
    def __init__(self,elem):
        self.elem=elem
        self.next=None #下一个节点
        self.prev=None #前一个节点

class DoubleLinkedList:
    # 双向链表初始化
    def __init__(self, node=None):
        # 判断node是否为空
        if node != None:
            headNode=Node(node)
            self._head=headNode
        else:
            self._head=node
    def is_empty(self):
        '''
        if self._head==None:
            print("True")
        else:
            print("False")
            '''
        return self._head==None
    #计算链表长度
    def length(self):
        count=0
        curNode=self._head
        while curNode!=None:
            count+=1
            curNode=curNode.next
            return count
    #遍历链表
    def travel(self):
        curNode=self._head
        while curNode!=None:
            print(curNode.elem,end='\t')
            curNode=curNode.next
        print("  ")
    #在头部添加元素
    def add(self,item):
        #判断是否空链表
        node = Node(item)
        if self.is_empty():
            self._head=node
        else:
            #将传入的值构造成节点
            node=Node(item)
            #将新节点的链接域next指向头节点
            node.next=self._head
            #将_head的头节点的prev指向node
            self._head.prev=node
            #将链表的头_head指向新节点
            self._head=node
    #在尾部追加元素
    def append(self,item):
        #将传入的值构造成节点
        node=Node(item)
        if self.is_empty(): #双向链表为空
            self._head=node
        else: #双向链表不为空
            curNode=self._head
            while curNode.next!=None:
                curNode=curNode.next
            #修改节点，最后一个节点的next指向node
            curNode.next=node
            #将node节点的前驱指向当前节点
            node.prev=curNode

    #在指定位置添加元素
    def insert(self,pos,item):
        #如果pos<=0，默认插入到头部
        if pos<=0:
            self.add(item)
        #如果pos>链表长度，直接在尾部追加
        elif pos>(self.length()-1):
            self.append(item)
        else:
            #构造节点
            node=Node(item)
            count=0
            curNode=self._head
            while count<(pos-1): #查找前一个节点
                count+=1
                curNode=curNode.next
            #修改指向
            #node节点前驱指向当前节点
            node.prev=curNode
            #node节点的next指向当前节点的下一个节点
            node.next=curNode.next
            #当前节点的下一个节点的前驱指向node节点
            curNode.next.prev=node
            #当前节点的下一个节点指向node节点
            curNode.next=node

    #查找节点是否存在
    def search(self,item):
        curNode=self._head
        while curNode!=None:
            if curNode.elem==item:
                return True
            curNode=curNode.next
        return False
    #删除节点
    def remove(self,item):
        curNode=self._head
        while curNode!=None:
            if curNode.elem==item:
                #判断是否是头节点
                if curNode==self._head:#是头节点
                    self._head=curNode.next
                    #判断当前节点是否只有一个节点
                    if curNode.next:
                        curNode.next.prev==None
                else:
                    #删除
                    curNode.prev.next=curNode.next
                    #判断当前节点是否是最后一个节点，若是，不需要移动下一个
                    if curNode.next:
                        curNode.next.prev=curNode.prev
            break
        else:
                curNode=curNode.next
if __name__=="__main__":
    doubleLinkedList=DoubleLinkedList()
    print("-----头部添加-----")
    doubleLinkedList.add(11)
    doubleLinkedList.add(22)
    doubleLinkedList.add(33)
    doubleLinkedList.travel()
    print("-----尾部追加-----")
    doubleLinkedList.append(44)
    doubleLinkedList.travel()
    print("指定位置插入")
    doubleLinkedList.insert(3,100)
    doubleLinkedList.travel()
    print("-----删除元素-----")
    doubleLinkedList.remove(33)
    doubleLinkedList.travel()

 —–头部添加—–
33    22    11      
—–尾部追加—–
33    22    11    44      
指定位置插入
33    22    11    44    100      
—–删除元素—–
22    11    44    100