[数据结构与算法]Python实现单链表的节点类，增删改查操作

?1、创建单链表节点的类：

? ? ?包含两个成员变量：next 指针 和 value值

2、定义单链表的类

? ? 包含一个成员变量：单链表的头指针，初始化为None

3、定义单链表的操作：

（1）单链表初始化

（2）是否非空

（3）求链表长度

（4）链表元素查询

（5）链表插入元素X：头、尾和指定位置

（6）链表删除元素X

4、查询、插入和删除的时间复杂度

（1）查找 时间复杂度： O(n)

（2）插入和删除，由于要从头查找前驱结点，所耗时间复杂度为O(n)，插入和删除本身的操作时间复杂度是O(1)

#定义单链表的节点
class linknode:
    def __init__(self,val):
        '''实例化单链表的类时：定义两个成员变量：一个是head指针，一个是节点存储的值'''
        self.val = val
        self.next = None

#定义单链表类：并定义单链表的成员函数：增删改查
class linklist:
    def __init__(self):
        self.head=None

    #初始化单链表
    def init_linklist(self,data):
        self.head = linknode(data[0])  #创建头节点，头节点的值存放data的第0个元素
        r = p = self.head
        for i in data[1:]:
            node = linknode(i)
            p.next = node
            p = p.next
        return r

    #判断单链表是否为空
    def is_empty(self):
        return self.head==None

    #获取单链表的长度
    def length(self):
        count = 0
        cur = self.head  #定义游标
        while cur != None:
            count +=1
            cur = cur.next
        return count

    #遍历整个链表
    def travel(self):
        cur = self.head  #定义游标
        while cur != None:
            print(cur.val,end=' ')
            cur = cur.next

    #单链表查询指定元素x所在的位置
    def search(self,x):
        cur = self.head #定义游标
        count = 0
        while cur!= None:
            if cur.val==x:
                return count
            else:
                cur = cur.next
                count += 1
        return -1

    #单链表表头增加元素x
    def insert_to_head(self,x):
        node = linknode(x)
        node.next = self.head
        self.head = node

    #单链表末尾增加元素x
    def insert_to_end(self,x):
        node = linknode(x)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next !=None:
                cur = cur.next
            cur.next = node

    #单链表指定位置添加元素x
    def insert_to_index(self,x,pos):
        if pos<=0:
            self.insert_to_head(x)
        elif pos> (self.length() -1):
            self.insert_to_end(x)
        else:
            cur = self.head
            count = 0
            node = linknode(x)
            while count<pos-1:  #从0开始，循环结束后 cur指向 要插入元素的上一个节点
                count += 1
                cur = cur.next
            node.next = cur.next #先：新的节点的next指向原来该位置的节点，再：当前节点的next指向新的节点
            cur.next = node

    #删除值为x的节点
    def delete(self,x):
        cur = self.head
        while cur != None:
            if cur.val == x:
                if cur == self.head:
                    self.head = cur.next
                else:
                    cur.next = cur.next.next
                    break
            else:
                cur = cur.next


if __name__=='__main__':
    l = linklist()
    #l.init_linklist(['a','b','c','d',1,9,10,8,0])
    print(l.is_empty())
    l.insert_to_head(10)
    l.insert_to_end(0)
    l.insert_to_index(9,1)
    l.insert_to_index(8,2)
    l.insert_to_index(7,3)
    l.insert_to_index(6,4)
    print(l.length())
    print(l.search(9))
    l.travel()
    l.delete(8)
    print('')
    l.travel()



True
6
1
10 9 8 7 6 0 
10 9 8 6 0 
Process finished with exit code 0