单向链表
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

链表的特点
      1 单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
      2 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
      3 结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

实现链表
能实现链表的语言有很多，这里我们使用Python语言来实现，不多说了，直接上代码：

[Python] 纯文本查看 复制代码

class Node(object):
    """节点"""
    def __init__(self, data):
        # 数据域
        self.data = data
        # 引用域
        self.next = None

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

    def is_empty(self):
        """判断链表是否为空"""
        if self.__head == None:
            return True
        else:
            return False

    def add(self, data):
        """链表头部添加元素"""
        node = Node(data)
        node.next = self.__head
        self.__head = node

    def show(self):
        """遍历整个链表"""
        cur = self.__head

        while cur != None:
            # 当cur指向当不为空，说明该节点是有效节点
            print(cur.data, end=" --> ")
            cur = cur.next
        print()

    def append(self, data):
        """链表尾部添加元素"""
        cur = self.__head

        if s.is_empty():
            s.add(data)
            return

        # 当cur不是尾部节点的时候，我就偏移（cur = cur.next）
        while cur.next != None:
            cur = cur.next

        # cur指向的就是尾部节点
        node = Node(data)
        cur.next = node

    def length(self):
        """链表长度"""
        cur = self.__head
        count = 0

        while cur != None:
            # cur是一个有效的节点
            count += 1
            cur = cur.next

        return count

    def search(self, data):
        """查找节点是否存在"""
        cur = self.__head

        while cur != None:
            # cur是一个有效的节点
            if cur.data == data:
                return True

            cur = cur.next

        return False

    def remove(self, data):
        """删除节点"""
        cur = self.__head
        pre = None

        while cur != None:
            if cur.data == data:
                # cur当前节点就是我们要删除的节点
                if cur == self.__head:
                    # 当前要删除的节点正好是头节点
                    self.__head = self.__head.next
                    return

                pre.next = cur.next
                return

            # pre指向的就是cur的前置节点
            pre = cur
            cur = cur.next

    def insert(self, index, data):
        """指定位置添加元素"""
        # index <= 0
        # 插入头部
        if index <= 0:
            s.add(data)
            return

        # index > s.length()-1
        # 插入尾部
        if index > s.length() - 1:
            s.append(data)
            return

        cur = self.__head

        for i in range(index-1):
            cur = cur.next

        # cur指向的就是第index-1个节点
        node = Node(data)
        node.next = cur.next
        cur.next = node


if __name__ == "__main__":
    s = SingleLinkList()   # 测试

    print("is empty: ", s.is_empty())

    s.add(1)
    s.add(2)
    s.add(3)

    s.show()

    s.append(4)

    s.show()

    print("length: ", s.length())

    print("search: ", s.search(11))

    s.remove(2)
    s.remove(3)

    s.show()

    s.insert(2, 10)
    s.insert(1, 20)
    s.show()

    s.insert(-9, 777)
    s.insert(99999, 666)
    s.show()

单向链表
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

链表的特点
      1 单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
      2 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
      3 结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

实现链表
能实现链表的语言有很多，这里我们使用Python语言来实现，不多说了，直接上代码：

[Python] 纯文本查看 复制代码

class Node(object):
    """节点"""
    def __init__(self, data):
        # 数据域
        self.data = data
        # 引用域
        self.next = None

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

    def is_empty(self):
        """判断链表是否为空"""
        if self.__head == None:
            return True
        else:
            return False

    def add(self, data):
        """链表头部添加元素"""
        node = Node(data)
        node.next = self.__head
        self.__head = node

    def show(self):
        """遍历整个链表"""
        cur = self.__head

        while cur != None:
            # 当cur指向当不为空，说明该节点是有效节点
            print(cur.data, end=" --> ")
            cur = cur.next
        print()

    def append(self, data):
        """链表尾部添加元素"""
        cur = self.__head

        if s.is_empty():
            s.add(data)
            return

        # 当cur不是尾部节点的时候，我就偏移（cur = cur.next）
        while cur.next != None:
            cur = cur.next

        # cur指向的就是尾部节点
        node = Node(data)
        cur.next = node

    def length(self):
        """链表长度"""
        cur = self.__head
        count = 0

        while cur != None:
            # cur是一个有效的节点
            count += 1
            cur = cur.next

        return count

    def search(self, data):
        """查找节点是否存在"""
        cur = self.__head

        while cur != None:
            # cur是一个有效的节点
            if cur.data == data:
                return True

            cur = cur.next

        return False

    def remove(self, data):
        """删除节点"""
        cur = self.__head
        pre = None

        while cur != None:
            if cur.data == data:
                # cur当前节点就是我们要删除的节点
                if cur == self.__head:
                    # 当前要删除的节点正好是头节点
                    self.__head = self.__head.next
                    return

                pre.next = cur.next
                return

            # pre指向的就是cur的前置节点
            pre = cur
            cur = cur.next

    def insert(self, index, data):
        """指定位置添加元素"""
        # index <= 0
        # 插入头部
        if index <= 0:
            s.add(data)
            return

        # index > s.length()-1
        # 插入尾部
        if index > s.length() - 1:
            s.append(data)
            return

        cur = self.__head

        for i in range(index-1):
            cur = cur.next

        # cur指向的就是第index-1个节点
        node = Node(data)
        node.next = cur.next
        cur.next = node


if __name__ == "__main__":
    s = SingleLinkList()   # 测试

    print("is empty: ", s.is_empty())

    s.add(1)
    s.add(2)
    s.add(3)

    s.show()

    s.append(4)

    s.show()

    print("length: ", s.length())

    print("search: ", s.search(11))

    s.remove(2)
    s.remove(3)

    s.show()

    s.insert(2, 10)
    s.insert(1, 20)
    s.show()

    s.insert(-9, 777)
    s.insert(99999, 666)
    s.show()