数据结构与算法(python)_04_单循环链表双链表

链表

单向循环链表

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

操作

is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在

class Node2(object):
    def __init__(self,val):
        self.val = val
        self.next = None

class SinCycLinkedlist(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):
        #cur初始指向头节点
        if self.is_empty():
            return 0
        cur = self.__head
        count = 1 #循环条件改变以后，count 需要从1开始数
        while cur.next != self.__head: #空链表进不了循环，length = 0
            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.val, end=" ") # print去掉换行用end=" "
            cur = cur.next
        #循环中未打印尾节点，循环外补打印
        print(cur.val)
    
    def add(self, val): # 头插
        node = Node2(val)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            #添加的节点指向_head
            node.next = self.__head
            # 移到链表尾部，将尾部节点的next指向node
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            #_head指向添加node的
            self.__head = node
        
    def append(self,val): # 尾插
        node = Node2(val)
        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 search(self,val):
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.val == val:
                return True
            else:
                cur = cur.next
        #循环不包括尾节点，补充判断
        if cur.val == val:
            return True
        return False
    
    def insert(self, pos, val): #任意位置插入
        if pos <=0: #就是头插法
            self.add(val)
        elif pos > (self.length()-1):#最后一位的下标为length-1,因为从0开始
            self.append(val)
        else:
            # pos 是从0开始的
            node = Node2(val)
            cur = self.__head
            count = 0
            while count < (pos -1):
                count += 1
                cur = cur.next
            #当循环退出时，指针指向指定位置前一个位置
            node.prev = cur
            node.next = cur.next
            #这里要注意顺序
            cur.next.pre = node
            cur.next = node
    
    def remove(self,val):
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.val == val:
                #判断是否为头节点
                if cur == self.__head:
                    #找尾节点
                    rear = self.__head
                    while cur.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
         #循环不包括尾节点，补充判断
        if cur.val == val:
            #如果只有一个节点
            if cur == self.__head:
                self.__head = None
            else:
                pre.next = cur.next

双链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

操作

is_empty() 链表是否为空
length() 链表长度
travel() 遍历链表
add(item) 链表头部添加
append(item) 链表尾部添加
insert(pos, item) 指定位置添加
remove(item) 删除节点
search(item) 查找节点是否存在

class Node(object):
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class DLinkedList(object):
    # 如果先有一个ListNode，可以传入linklist中，也可以不传，构建空链表
    #本身需要保存一个头节点属性
    #私有属性，__head
    def __init__(self,node=None):
        self.__head = node
    def listhead(self):
        return self.__head
    
    def is_empty(self):
        return self.__head == None
    
    def length(self):
        #cur初始指向头节点
        cur = self.__head
        count = 0 #用来数数
        while cur != None: #空链表进不了循环，length = 0
            count += 1
            #指针向下一个移动
            cur = cur.next
        return count
    
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.val, end=" ") # print去掉换行用end=" "
            cur = cur.next
    
    def add(self, val): # 头插
        node = Node(val)
        if self.is_empty():
            self.__head = node
        else:
            node.next = self.__head
            self.__head.prev = node
            self.__head = node
        
    def append(self,val): # 尾插
        node = Node(val)
        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 search(self,val):
        cur = self.__head
        while cur != None:
            if cur.val == val:
                return True
            else:
                cur = cur.next
        return false

指定位置插入节点

    def insert(self, pos, val): #任意位置插入
        if pos <=0: #就是头插法
            self.add(val)
        elif pos > (self.length()-1):#最后一位的下标为length-1,因为从0开始
            self.append(val)
        else:
            # pos 是从0开始的
            node = Node(val)
            cur = self.__head
            count = 0
            while count < (pos -1):
                count += 1
                cur = cur.next
            #当循环退出时，指针指向指定位置前一个位置
            node.prev = cur
            node.next = cur.next
            #这里要注意顺序
            cur.next.pre = node
            cur.next = node

删除元素

    def remove(self,val):
        if self.is_empty():
            return
        else:
            cur = self._head
            # 如果首节点就是要删除节点
            if cur.val == val:
                # 如果链表只有一个节点
                if cur.next == None:
                    self.head = None
                else:
                    #将第二个节点的prev设为None
                    cur.next.prev = None
                    # 将__head指向第二个节点
                    self.__head = cur.next
                return
            while cur != None:
                if cur.val == val:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                    break
                cur = cur.next