概念图

image.png

• 单链表是由一些具体的结点组成
• 每个结点都是一个对象，有直自己的标识
• 结点之间通过指针单项链接而成

表示链表结束，用结点的指针域指向空

表头添加数据

首先将新结点指向第一个结点，在将头指针指向新结点

image.png

一般情况添加数据

将新结点指针区域指向当前结点的next区域，将当前结点的next区域指向新节点

image.png

删除结点

image.png

python实现单链表

单链表结点构造

class Node:
    """
    单链表结点
    """
    def __init__(self, value):
        self.data = value
        self.next = None

单链表具体实现

class SingleLinkList:
    def __init__(self):
        self.__head = None

    def is_empty(self):
        """
        判断链表是否为空
        :return:
        """
        return self.__head is None

    def length(self):
        """计算链表的长度"""
        cur = self.__head
        i = 0
        while cur is not None:
            cur = cur.next
            i += 1
        return i

    def append(self, value):
        """在链表尾部添加"""
        node = Node(value)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def add(self, value):
        """在链表头部添加数据"""
        node = Node(value)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            node.next = cur
            self.__head = node

    def insert(self, index, value):
        """指定位置插入数据"""
        node = Node(value)
        cur = self.__head
        if index <= 0 or cur is None:
            self.add(value)
        elif index > self.length() - 1:
            self.append(value)
        else:
            count = 0
            while cur.next is not None and count < index - 1:
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def pop(self, index=0):
        """指定位置删除，默认删除第一个元素"""
        if not self.is_empty():
            if index == 0:
                cur = self.__head
                self.__head = cur.next
                return cur.data
            else:
                cur = self.__head
                pre = None
                count = 0
                if index > self.length()-1:
                    raise IndexError("索引超出范围")
                while cur.next is not None and count != index:
                    count += 1
                    pre = cur
                    cur = cur.next
                pre.next = cur.next
                return cur.data

    def remove(self, value):
        """指定数据第一个删除"""
        cur = self.__head
        pre = None
        while cur is not None:
            if cur.data == value:
                if not pre:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, value):
        """查询数据是否在链表中，返回第一个数据的索引， 没有则返回 -1"""
        if self.is_empty():
            return -1
        else:
            cur = self.__head
            count = 0
            while cur is not None:
                if cur.data == value:
                    return count
                count += 1
                cur = cur.next
            return -1

    def __repr__(self):
        data = []
        cur = self.__head
        while cur is not None:
            data.append(str(cur.data))
            cur = cur.next
        return "->".join(data)


if __name__ == '__main__':
    link_list = SingleLinkList()
    link_list.append(10)
    link_list.append(1)
    link_list.append(0)
    link_list.add(2)
    link_list.insert(2, 16)
    print(link_list.length())
    print(link_list)
    print(link_list.search(3))