【稳住，can win】Python双向链表和单向循环链表

【稳住，can win】Python双向链表和单向循环链表 代码实现

实现简易版本的双向不循环链表和单向循环链表。定义了头插、尾插、任意位置插入、删除和查找函数接口。

双向链表

class Node():
    def __init__(self, data):
        self.data = data
        self.pre = None
        self.next = None
class DoublelinkList():
    def __init__(self):
        self._head = None
        self._end = None

    def add(self, data):
        node = Node(data)

        if self._head is None:
            self._head = node
            node.pre = None
        else:
            node.next = self._head
            node.pre = None

            self._head.pre = node
            self._head = node

        self._end = node
    
    def append(self, data):
        node = Node(data)
        cur = self._head

        while cur and cur.next:
            cur = cur.next

        if cur is None:
            self.add(data)
        else:
            cur.next = node
            node.pre = cur
        self._end = node

    def get_size(self):
        cur = self._head
        cnt = 0
        while cur:
            cur = cur.next
            cnt += 1
        return cnt

    def insert(self, data, pos):
        node = Node(data)
        cur = self._head
        pre = None
        if pos <= 0:
            self.add(data)
        elif pos >= self.get_size():
            self.append(data)
        else:
            while pos:
                pre = cur
                cur = cur.next
                pos -= 1
            node.next = cur
            node.pre = pre

            cur.pre = node
            pre.next = node

    def remove(self, data):
            if self.get_size() <= 0:
                return
            cur = self._head
            pre = None
            while cur:
                if cur.data == data:
                    cur.next.pre = pre
                    pre.next = cur.next
                    break
                else:
                    pre = cur
                    cur = cur.next
    
    def search(self, data):
        cur = self._head
        pos = 0

        while cur:
            if cur.data == data:
                return pos
            else:
                cur = cur.next
                pos += 1
        return -1

    def r_travel(self):
        cur = self._end
        while cur:
            print("{}".format(cur.data), end="->")
            cur = cur.pre
        print("null")


    def travel(self):
        cur = self._head
        while cur:
            print("{}".format(cur.data), end="->") -> None
            cur = cur.next
        print("null")

if __name__ == "__main__":
    l = DoublelinkList()

    l.append(3)
    l.travel()

    l.add(0)
    l.add(1)
    l.append(4)
    l.travel()
    l.r_travel()

    l.insert(5, 2)
    l.r_travel()

    l.remove(3)
    l.r_travel()

测试结果

单向循环链表

class Node():
    def __init__(self, data):
        self.data = data
        self.next = None

class SingleCyclelinkList():
    def __init__(self):
        self._head = None
    
    def add(self, data):
        node = Node(data)

        if self._head is None:
            self._head = node
            node.next = self._head
        else:
            node.next = self._head

            cur = self._head
            while cur.next is not self._head:
                cur = cur.next
            cur.next = node
            self._head = node


    def append(self, data):
        node = Node(data)
        cur = self._head
        while cur:
            if cur.next == self._head:
                node.next = self._head
                cur.next = node
                break
            else:
                cur = cur.next

    def get_size(self):
        cnt = 0
        cur = self._head
        while cur:
            if cur.next == self._head:
                cnt += 1
                break
            else:
                cur = cur.next
                cnt += 1
        return cnt

    def insert(self, data, pos):
        node = Node(data)
        cur = self._head
        pre = None
        if pos <= 0:
            self.add(data)
        elif pos >= self.get_size():
            self.append(data)
        else:
            while pos:
                pre = cur
                cur = cur.next
                pos -= 1

            node.next = cur
            pre.next = node


    def remove(self, data):
        cur = self._head
        pre = None

        while cur:
            if cur.data == data:
                pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    
    def search(self, data):
        cur = self._head
        pos = 0
        while cur and cur.next is not self._head:
            if cur.data == data:
                return pos
            else:
                cur = cur.next
            pos += 1
        return -1

    def travel(self):
        cur = self._head

        while cur:
            if cur.next is  self._head:
                print("{}".format(cur.data), end="->")
                break
            else:
                print("{}".format(cur.data), end="->")
                cur = cur.next
        print("null")

if __name__ == "__main__":
    l = SingleCyclelinkList()

    l.insert(1,0)
    l.insert(2,0)
    l.insert(3,4)
    l.insert(3,5)
    l.insert(5,2)
    l.travel()

    l.remove(3)
    l.travel()

    print(l.search(5))

测试结果