数据结构-链表

python实现单链表

class Node(object):
    """结点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None


class SingleLinkList(object):
    """单链表"""
    def __init__(self, Node = None):
        self.__head = Node

    def is_empty(self):
        return self.__head == None

    def length(self):
        cur = self.__head
        cnt = 0
        while cur != None:
            cnt += 1
            cur = cur.next
        return cnt

    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

    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

    def insert(self, pose, item):
        """在指定位置插入结点"""
        if pose<=0:
            self.add(item)
        elif pose >= self.length():
            self.append(item)
        else:
            node = Node(item)
            cnt = 0
            cur = self.__head
            pre = None
            while cnt != pose:
                pre = cur
                cur = cur.next
                cnt += 1
            cur = node
            cur.next = pre.next
            pre.next = cur

    def remove(self, item):
        if self.is_empty():
            print("链表为空，删除操作错误！")
        else:
            cur = self.__head
            pre = None
            if cur.elem == item:
                self.__head = cur.next
                del cur
                return
            while cur.elem != item:
                pre = cur
                cur = cur.next
                if cur is None:
                    print("当前链表未找到要删除的元素！")
                    return
            pre.next = cur.next
            print("删除成功！")
            del cur

    def search(self, item):
        cur = self.__head
        pos = 1
        while cur.elem != item:
            cur = cur.next
            pos +=1
            if cur is None:
                print("当前链表查无此元素！")
                return
        print(f"查找成功,该元素在链表中的第{pos}个位置")

if __name__ == "__main__":
    slinklist = SingleLinkList()
    slinklist.add('abc') # 链表头部添加元素
    slinklist.add('小明')
    slinklist.append(1) # 链表尾部添加元素
    slinklist.append(100) 
    slinklist.remove("abcd") # 移除链表中的元素
    slinklist.search(1) # 在链表中查找某个元素
    slinklist.insert(5, "hello world")
    print(f"当前链表长度为{slinklist.length()}")
    slinklist.travel() # 遍历链表中的元素并打印
    print(slinklist.is_empty())