定义

单向链表也叫做单链表，是链表中最简单的一种形式，他的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域指向一个空值(None)
image.png

说明

  1. 表元素域elem用来存放具体的数据
  2. 链接域next用来存放下一个节点的位置（Python中的标识）指向下一个结点
  3. 变量p指向链表的头节点（首结点）的位置，从p出发能找到表中的任意节点。

功能实现

  1. Node结点

    1
    2
    3
    4
    class Node(object):
        def __init__(self,item):
            self.item = item
            self.next = None

  2. 链表初始化

    1
    2
    3
    4
    5
    6
    7
    class SingleLinkList:
        def __init__(self,node = None):
            if node != None: # 不为空的话，创建结点作为头结点
                headNode = Node(node)
                self.__head = headNode
            else:
                self.__head = node  #相当于等于None

  3. 判断是否为空

    1
    2
    def is_empty(self):
        return self.__head == None #根据头结点是否是空来判断

  4. 链表长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def length(self):
        # 获取链表长度
        cur = self.__head
        count = 0
        #不断next直到直到最末尾None
        while cur!=None:
            count+=1
            cur = cur.next
        return count

  5. 遍历链表

    1
    2
    3
    4
    5
    6
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.item,end=" ")
            cur = cur.next
        print("")

  6. 头部添加元素

    1
    2
    3
    4
    5
    6
    7
    def add(self,item):
        #首先创造结点
        node = Node(item)
        # 结点指向头部
        node.next = self.__head
        #__head指向当前node结点
        self.__head = node

  7. 尾部添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def append(self,item):
        # 首先创造结点
        node = Node(item)
        #判断链表是否为空，如果是空的话，那么就是头结点
        if self.is_empty():
            self.__head = node # 把当前结点当作头结点
        else:
            # 从头结点一直找到最后一个，将最后的一个next指向当前的node结点
            curNode = self.__head
            while curNode.next != None:
                curNode = curNode.next
            curNode.next = node

  8. 指定位置添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def insert(self,pos,item):
        # 若指定位置pos为第一个元素之前，则执行头部插入
        if pos <=0:
            self.add(item)
        # 若指定位置pos超过链表尾部，则执行尾部插入
        elif pos > (self.length()-1):
            self.append(item)
        else:
            # 首先创造结点
            node = Node(item)
            count = 0
            pre = self.__head
            while count < (pos-1):
                count +=1
                pre = pre.next
            # 前一个结点指向的现在变成node指向
            node.next =pre.next
            # 前一个结点现在指向node结点
            pre.next = node

  9. 删除元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def remove(self,item):
        cur = self.__head
        pre = None
        while cur != None:
            if cur.item == item:
                #如果第一个就是删除的元素
                if not pre : # pre没有发生变化，说明第一个就是删除的元素
                    self.__head = cur.next # 头结点直接指向第二个元素
                else:
                    #将删除位置前一个结点的next指向删除位置的后一个结点
                    pre.next = cur.next
                break
            else:
                # pre存的就是上一个结点
                pre = cur
                # cur存的就是下一个结点
                cur = cur.next

  10. 查找元素

    1
    2
    3
    4
    5
    6
    7
    8
    def search(self,item):
        cur = self.__head
        while cur != None:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
if __name__ == '__main__':
    #初始化元素值为 20 的单向链表

    # singleLinkList=SingleLinkList(20)
    #初始化一个空的单向链表

    singleLinkList=SingleLinkList()
    print('是否是空链表：',singleLinkList.is_empty())
    print('链表的长度：',singleLinkList.length())
    print('----------遍历单链表----------')
    singleLinkList.travel()
    print('--------查找---------')
    print(singleLinkList.search(20))
    print(singleLinkList.search(30))
    print('------头部插入-----------')
    singleLinkList.add(1)
    singleLinkList.add(2)
    singleLinkList.add(3)
    singleLinkList.travel()
    print('------尾部追加-----------')
    singleLinkList.append(10)
    singleLinkList.append(20)
    singleLinkList.append(30)
    singleLinkList.travel()
    print('链表的长度：', singleLinkList.length())
    print('----------指定位置插入----------')
    singleLinkList.insert(2,100)
    singleLinkList.travel()
    singleLinkList.insert(-1, 200)
    singleLinkList.travel()
    singleLinkList.insert(100, 300)
    singleLinkList.travel()
    print('---------删除节点--------')
    singleLinkList.remove(100)
    singleLinkList.travel()
    singleLinkList.remove(200)
    singleLinkList.travel()
    singleLinkList.remove(300)
    singleLinkList.travel()

image.png