python链表之单向链表实践

链表是一种常见的数据结构，属于线性表的一种，但不会按照线性的顺序存储数据。

由于不按照顺序存储，链表在存储的时候是O(1)的复杂度。

链表包含：单向链表、双向链表、循环链表、块状链表

本文主要是单向链表的实践，也是链表中最简单的一种，它包含了两个域，一个用于数据存储，一个指向下一个节点，而最后一个节点指向None。

单向链表只可以往一个方向遍历，这也是名字的由来。

实践代码：

# -*- encoding: utf-8 -*-
"""
@File    : singleLinkedList
@Author  : TopAbu.com
@Software: IntelliJ IDEA
"""
# 1.定义节点类：item、next
# 2.定义单向链表类：定义一个属性保存头节点（需要根据头节点获取后续所有节点）


class Node(object):
    name = '节点类'

    def __init__(self, item):
        self.item = item
        self.next = None

    def __repr__(self):
        return str(self.item)


class SingleLinkedList(object):
    name = '单向链表'

    def __init__(self):
        self.__head = None

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

    def length(self):
        '''返回链表的长度'''
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''打印链表中的每一个元素'''
        cur = self.__head
        while cur is not None:
            print(cur.item)
            cur = cur.next

    def search(self, item):
        '''查找某一元素是否在链表中'''
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

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

    def append(self, item):
        '''在尾部添加元素'''
        node = Node(item)
        if self.is_empty():
            self.__head = node
        cur = self.__head
        while cur.next is not None:
            cur = cur.next
        cur.next = node

    def insert(self, item, pos):
        '''
        在指定位置添加元素
        item -> 元素
        pos -> 插入位置
        '''
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            count = 0
            cur = self.__head
            node = Node(item)
            while count < (pos - 1):
                cur = cur.next
                count += 1
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        '''删除节点，默认删除一个元素'''
        cur = self.__head
        pre = None
        while cur is not None:
            if cur.item == item:
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    cur.next = None
                    pre.next = cur.next
                return
            pre = cur
            cur = cur.next


if __name__ == '__main__':
    ll = SingleLinkedList()
    print(ll.is_empty())
    print(ll.length())
    ll.add(1)
    print(ll.search(1))
    ll.append('a')
    ll.add('b')
    ll.insert('p', 2)
    print('*'*20)
    ll.travel()
    print('*'*20)
    ll.remove('p')
    ll.travel()