本文主要介绍了Python开发入门到精通--Python数据结构之单链表，通过具体的内容展现，希望对大家Python语言的学习有所帮助。

今天终于把大学都没想明白的链表数据结构整明白了，也算小小的收获，挺好玩的。文后附链表操作示意图。

单向链表(单链表)是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域，一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

isempty(self) 链表是否为空

length(self) 链表长度

travel(self) 遍历整个链表

add(self,item) 链表头部添加元素

append(self,item) 链表尾部添加元素

insert(self,item,index) 指定位置添加元素

deletebyitem(self,item) 根据数据项删除节点

deletebyindex(self,index) 根据索引位置删除节点

search(self,item) 根据数据项查找节点是否存在

update(self,index,item) 暂无实现

getitem(self,index) 获取索引位置对应的数据项

getindex(self,item) 获取数据项对应的索引位置

代码基本为原创，经过大量重写

class Node(object):

    def __init__(self, item):

        self.item = item

        self.next = None

    def __repr__(self):

        pass

    def __str__(self):

        return str(self.item)

class SingleLinkList(object):

    def __init__(self):

        self.header = None

        self.currentnum=0

    def isempty(self):

        return self.header == None

    def length(self):

        return self.currentnum

    def travel(self):

        cur =self.header

        while cur !=None:

            print("{}".format(cur.item),end=" ")

            cur=cur.next

        print("\r")

    def add(self,item):

        node=Node(item)

        # 新节点的链接指向头节点

        node.next=self.header

        # 链表的头指向新节点

        self.header=node

        self.currentnum+=1

    def append(self,item):

        tempnode=self.header

        node=Node(item)

        if self.isempty():

            self.add(node)

        else:

            while tempnode.next!=None:

                tempnode=tempnode.next

            tempnode.next=node

            self.currentnum+=1

    def insert(self,item,index):

        node=Node(item)

        tempnode=self.header

        if index>self.currentnum+1 or index<=0:

            raise IndexError("{} is not find in Linklist".format(index))

        # 指定位置为第一个即在头部插入

        if index==1:

            self.add(node)

        elif index>self.currentnum-1:

            self.append(node)

        else:

            for i in range(1,index-1):

                tempnode=tempnode.next

            node.next=tempnode.next

            tempnode.next=node

            self.currentnum+=1

    def deletebyitem(self,item):

        tempnode=self.header

        prenode=None

        while tempnode!=None:

            if tempnode.item==item:

                if tempnode==self.header:

                    self.header=tempnode.next

                else:

                    prenode.next=tempnode.next

                break

            else:

                prenode=tempnode

                tempnode=tempnode.next

    def deletebyindex(self,index):

        if index>self.currentnum or index<=0:

            raise IndexError("{} is not find in Linklist".format(index))

        i=1

        tempnode=self.header

        prenode=self.header

        if index==1:

            self.header = tempnode.next

            self.currentnum-=1

            return

        while tempnode.next and i<index:

            prenode = tempnode

            tempnode = tempnode.next

            i+=1

        if i==index:

            prenode.next=tempnode.next

            self.currentnum-=1

    def search(self,item):

        tempnode=self.header

        while tempnode!=None:

            if tempnode.item==item:

                return True

            else:

                tempnode=tempnode.next

        return False

    def update(self,index,item):

        pass

    def getitem(self,index):

        if index<=0 or index>self.currentnum:

            raise IndexError("{} is not find in Linklist".format(index))

        tempnode=self.header

        i=1

        while i<index:

            tempnode=tempnode.next

            i+=1

        return tempnode.item

    def getindex(self,item):

        tempnode = self.header

        i=0

        flag=False

        while tempnode != None:

            i+=1

            if tempnode.item == item:

                flag=True

                return i

            else:

                tempnode = tempnode.next

        if flag==False:

            return 0

if __name__ == '__main__':

    a = SingleLinkList()

    a.add(1)  # 1

    print('a.add(1)')

    a.travel()

    a.add(2)  # 2 1

    print('a.add(2)')

    a.travel()

    a.append(3)  # 2 1 3

    print('a.append(3)')

    a.travel()

    a.insert(4, 2)  # 2 1 4 3

    print('a.insert(2, 4)')

    a.travel()

    print('a.search(1)=',a.search(1))

    print('a.search(5)=', a.search(5))

    print('a.getindex(1)=',a.getindex(1))

    print('a.getindex(5)=', a.getindex(5))

    print('a.getitem(2)=', a.getitem(2))

    print('a.getitem(4)=', a.getitem(4))

    print('a.getitem(3)=', a.getitem(3))

    # a.deletebyitem(5)

    # print('a.deletebyitem(5)')

    # a.travel()

    # a.deletebyitem(4)

    # print('a.deletebyitem(4)')

    # a.travel()

    # a.deletebyitem(2)

    # print('a.deletebyitem(2)')

    # a.travel()

    a.deletebyindex(4)

    print('a.deletebyindex(4)')

    a.travel()

    a.deletebyindex(2)

    print('a.deletebyindex(2)')

    a.travel()

    a.deletebyindex(1)

    print('a.deletebyindex(1)')

    a.travel()

结果如下

C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/linklist.py

a.add(1)

1  

a.add(2)

2 1  

a.append(3)

2 1 3  

a.insert(2, 4)

2 4 1 3  

a.search(1)= True

a.search(5)= False

a.getindex(1)= 3

a.getindex(5)= 0

a.getitem(2)= 4

a.getitem(4)= 3

a.getitem(3)= 1

a.deletebyindex(4)

2 4 1  

a.deletebyindex(2)

2 1  

a.deletebyindex(1)

1  

Process finished with exit code 0

链表头部增加节点示意图

从链表尾部增加节点示意图

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评