目录

第三章

链表的提出

python中变量标识的本质

单链表

单链表与顺序表的对比

双向链表

单向循环链表

第三章

链表的提出

线性表：顺序表+链表

顺序表是按顺序排列的，链表是用线串起来的（可以随意添加、删除元素）

链表操作的要点是搞清楚先切断谁，再连接谁

Li=[200,400,600]

三个单链表节点如下：

python中变量标识的本质

python中的地址是什么数据类型？

a = 10

b = 20

a,b = b,a（改变的只是a,b存储单元中的地址）

a和b是存储单元，存储的是10，20这两个数值的地址

python中=就是产生一个引用的链接

单链表

单向链表指箭头方向必须从前一个节点指向后一个节点（数据区+后继节点）

第一个节点叫头节点，最后一个节点叫尾节点（空）

单链表中每个单元（节点）有两部分，一个是元素，一个是下一个节点的标识

class SingleNode(object):
    def __init__(self,item):   
        """单链表的结点"""
        self.item = item   # _item存放数据元素
        self.next = None   # _next是下一个节点的标识

基本操作会有两个类产生，一个是节点类，一个是链表类

is_empty()链表是否为空
length()链表长度
travel()遍历整个链表：可以打印出链表中每个节点
add(item)链表头部添加元素
append(item)链表尾部添加元素
insert(pos,item)指定位置添加元素
remove(item)删除节点---删除从列表头找到的第一个元素
search(item)查找节点是否存在

# coding:utf-8
class Node(object):
    """"节点的类"""
    def __init__(self,elem):
        self.elem = elem
        self.next = None
    pass
# node = Node(100)
class SingleLinkList(object):
    """单链表的类"""
    def __init__(self,node=None):
        self.__head = node # 对外不暴露的私有属性 头加__
    def is_empty(self): # 这些都是对象操作self
        """链表是否为空"""
        return self.__head == None #判断为空
    def length(self):
        """链表长度"""
        cur = self.__head  # cur游标，用来移动遍历节点
        count = 0  # count记录数量，判断最后的位置
        while cur != None:  # cur不等于None
            count += 1
            cur = cur.next
        return count
    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur != None:
            print(cur.elem,end=' ') # python3中,end=''代表禁止换行————python2中仅用，即可
            cur = cur.next
            # print("") #换行
    def add(self,item): # 需要反传参数
        """链表头部添加元素，头插法"""
        node = Node(item) #首先构造要插入的节点
        node.next = self.__head  #让节点的尾部指向原链表的头部
        self.__head = node
    def append(self,item):
        """链表尾部添加元素，尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node  # 先判断链表是否为空，若是空链表，则将_head指向新节点
        else:
            cur = self.__head # 若不为空，则找到尾部，将尾节点的next指向新节点
            while cur.next != None:
                cur = cur.next
            cur.next = node
    def insert(self,pos, item):
        """指定位置添加元素
        :param pos 从0开始索引
        """
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            pre = self.__head  # piror
            count = 0
            while count < (pos-1):
                pre = pre.next
                count +=1
            # 当循环推出后，pre指向 pos-1位置
            node.next = pre.next
            pre.next = node
    def remove(self,item):
        """删除节点"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断此节点是否为头节点
                if cur == self.__head:
                   self.__head = cur.next
                else:
                    pre.next = cur.next
                break #删完就退出循环
            else:
                pre = cur
                cur = cur.next
    def search(self,item):
        """查找节点是否存在"""
        cur = self.__head
        while cur != None: #cur不等于none才可以进入循环
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())
    ll.append(1)
    print(ll.is_empty())
    print(ll.length())
    ll.append(2)
    ll.add(8)
    ll.append(3)
    ll.append(4)
    ll.insert(-1,9)
    ll.insert(2,100)
    ll.insert(10,200)
    ll.travel()
    print("")
    print(ll.search(100))
    ll.remove(9)
    ll.travel()

后继节点：当前节点的下一个节点next

要遍历就要用循环while

单链表与顺序表的对比

链表不能一次性定位到pos，需要循环。顺序表可以一次定位。

链表的节点在内存中可以分散，但时间复杂度高了。顺序表的空间必须是连续的，而且顺序表存储空间不够时需要重新申请空间。

双向链表

双向链表中的节点与单链表不同，另外保存前面节点的位置。如下：

前驱节点+数据区+后继节点

 可以把类的代码进行封装，后面再建新的类的时候，把之前的类当作object，可以达到类的继承

class Node(object):
    def __init__(self,item):
        self.elem = item
        self.next = None
        self.prev = None
class DoubleLinkList(object):
    def __init__(self,node=None):
        self.__head = node
    def is_empty(self):
        """链表是否为空"""
        return self.__head is None
    def length(self):
        """链表长度"""
        cur = self.__head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        """遍历整个链表：可以打印出链表中每个节点"""
        cur = self.__head
        while cur != None:
            print(cur.elem,end=" ")
            cur = cur.next
    def add(self,item):
        """链表头部添加元素"""
        node = Node(item)
        node.next = self.__head
        self.__head = node # self.__head.prev = node  self.__head = node也可以
        node.next.prev = node
    def append(self,item):
        """链表尾部添加元素"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur
    def insert(self,pos, item):
        """指定位置添加元素"""
        if pos <=0: #从0开始数
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos :
                count +=1
                cur = cur.next
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node
    def remove(self,item):
        """删除节点 - --删除从列表头找到的第一个元素"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next: #如果cur.next存在，进入if，否则退出
                        # 判断链表是否只有一个节点
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next
    def search(self,item):
        """查找节点是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__" :
    dll = DoubleLinkList()
    print(dll.is_empty())
    print(dll.length())
    dll.append(1)
    print(dll.is_empty())
    print(dll.length())
    dll.append(2)
    dll.add(8)
    dll.append(9)
    dll.append(3)
    dll.append(4)
    dll.insert(-1, 9)
    dll.insert(2, 100)
    dll.insert(10, 200)
    dll.travel()
    print("")
    print(dll.search(100))
    dll.remove(9)
    dll.travel()

单向循环链表

单向循环链表是单链表的一种变形，链表中最后一个节点的next不再是None，而是指向链表的头节点。

class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.next = None
class SingleCycleLinkList(object):
    def __init__(self,node=None):
        self.__head = node
        if node:
            node.next = node
    def is_empty(self):
        """链表是否为空"""
        return self.__head == None
    def length(self):
        """链表长度"""
        if self.is_empty():
            return 0
        cur = self.__head
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        """遍历整个链表：可以打印出链表中每个节点"""
        if self.is_empty():
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem,end=" ")
            cur = cur.next
        print(cur.elem)
    def add(self,item):
        """链表头部添加元素"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            self.__head = node
            cur.next = self.__head  # node
    def append(self,item):
        """链表尾部添加元素"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            node.next = self.__head
    def insert(self,pos, item):
        """指定位置添加元素"""
        if pos <=0: #从0开始数
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            pre = self.__head
            count = 0
            while count < (pos-1) :
                pre = pre.next
                count +=1
            node.next = pre.next
            pre.next = node
    def remove(self,item):
        """删除节点 - --删除从列表头找到的第一个元素"""
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                if cur == self.__head:
                    # 头节点
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 中间节点
                    pre.next = cur.next
                return
            else:
                pre = cur
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            if cur == self.__head:
                self.__head = None
            else:
                pre.next = self.__head
    def search(self,item):
        """查找节点是否存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 退出循环，指向尾节点
        if cur.elem == item:
            return True
        return False

if __name__ == "__main__":
    ll = SingleCycleLinkList()
    print(ll.is_empty())
    print(ll.length())
    ll.append(1)
    print(ll.is_empty())
    print(ll.length())
    ll.append(2)
    ll.add(8)
    ll.append(9)
    ll.append(3)
    ll.append(4)
    ll.insert(-1, 9)
    ll.insert(2, 100)
    ll.insert(10, 200)
    ll.travel()
    print("")
    print(ll.search(100))
    ll.remove(9)
    ll.travel()