单向链表 Python实现

The core values of Chinese socialism

# 单位元素定义
class SingleNode(object):
    def __init__(self, item):
        self.item = item
        self.next = None

# 单向链表定义
class SingleLinkList(object):
    # 空链表
    def __init__(self):
        self._head = None

    # 空链
    def isEmpty(self):
        return self._head == None

    # 链表长度
    def length(self):
        cur = self._head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    # 遍历
    def travel(self):
        cur = self._head
        while cur:
        #while cur != None:
            print(cur.item, end=" ")
            cur = cur.next
        return None

    # 头添加
    def addFirst(self, item):
        node = SingleNode(item)
        node.next = self._head
        self._head = node

    # 尾添加
    def append(self, item):
        node = SingleNode(item)
        if self.isEmpty():
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node

    # 插入
    def insert(self, pos, item):
        if pos <= 0:
            self.addFirst(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = SingleNode(item)
            count = 0
            cur = self._head
            while count < (pos-1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    # 删除
    def remove(self, item):
        cur = self._head
        per = None
        while cur != None:
            if cur.item == item:
                # 删头结点，not None = 1, 执行
                if not per:
                    self._head = cur.next
                else:
                    per.next = cur.next
                break
            else:
                per = cur
                cur = cur.next

    # 查找
    def search(self, item):
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

if __name__ == '__main__':
    sll = SingleLinkList()
    sll.addFirst(20)
    sll.travel()
    print('')
    sll.addFirst(10)
    sll.travel()
    print('')
    sll.append(30)
    sll.travel()
    print('')
    sll.insert(2, 77)
    sll.travel()
    print('')
    print("Length of sll is {}".format(sll.length()))

    print("search 30", sll.search(30))
    print("search 32", sll.search(32))


    sll.remove(20)
    sll.travel()
    print('')
    print("Length of sll is {}".format(sll.length()))

Connected to pydev debugger (build 192.5728.105)
20
10 20
10 20 30
10 20 77 30
Length of sll is 4
search 30 True
search 32 False
10 77 30