Python实现链表

# coding:utf8#节点类
class Node():
    def __init__(self, _item):
        self.item = _item
        self.next = None

#链表类
class Link():
    def __init__(self):
        self._head = None

    def add(self, _item):
        node = Node(_item)
        node.next = self._head
        self._head = node

    def append(self, _item):
        node = Node(_item)
        cur = self._head
        pre = None
        # 链表为空,追加的为第一个节点时
        if cur == None:
            self._head = node
            return
        while cur:
            pre = cur
            cur = cur.next
        pre.next = node

    def insert(self, pos, _item):
        node = Node(_item)
        pre = None
        cur = self._head
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur

    def remove(self, _item):
        pre = None
        cur = self._head
        # 如果删除项为首部节点
        if cur.item == _item:
            self._head = cur.next
            return
        while cur:
            pre = cur
            cur = cur.next
            if cur == None:
                return
            if cur.item == _item:
                pre.next = cur.next
                return

    def search(self, _item):
        flag = False
        cur = self._head
        while cur:
            if cur.item == _item:
                flag = True
            cur = cur.next
        return flag

    def travel(self):
        cur = self._head
        while cur:
            print(cur.item)
            cur = cur.next

    def isEmpty(self):
        return self._head == Node

    def size(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count


if __name__ == "__main__":
    link = Link()
    link.add(1)
    link.add(2)
    link.add(3)
    link.append(4)
    link.append(5)
    link.insert(1, 7)
    link.travel()
    link.remove(5)
    link.travel()
    print(link.isEmpty())
    print(link.size())
    print(link.search(5))
    print(link.search(6))

相关推荐