Python--单向链表

单链表python实现

单链表

节点实现

# 节点
class Node(object):
    def __init__(self,item):
        #  item 存储数据元素
        self.item = item
        #  next为下一个节点标识
        self.next = None

单链表操作

# 单链表
class SingleLinkList(object):
    def __init__(self):
        self._head = None
    # 判空
    def is_empty(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):
        current = self._head
        strs = ''
        while current != None:
            strs = strs + "item:" + str(current.item) + ","
            current = current.next
        print(strs)
        return  strs

头部插入

头部插入

    # 头部添加
    def add(self,item):
        element = Node(item)
        current = self._head
        self._head = element
        element.next = current

尾部添加

    #  尾部添加
    def append(self,item):
        element = Node(item)
        if self.is_empty():
            self.add(item)
        else:
            current = self._head
            while current.next != None:
                current = current.next
            current.next = element
            element.next = None

在index位置插入

index 插入

    # 在第index位置插入元素
    def insert(self,index,item):
        current = self._head
        count = 0
        element = Node(item)
        length = self.length()
        if(index == 0):
            self.add(0)
        elif index > length - 1:
            self.append(item)
        else:
            while count != (index - 1) :
                count += 1
                current = current.next
            element.next = current.next
            current.next = element

删除结点

删除

    def remove(self,item):
        current = self._head
        pre = None
        while current != None:
            if item != current.item:
                pre = current
                current = current.next
            else:
                if not  pre:
                    self._head = current.next
                else:
                    pre.next = current.next



    def search(self,item):
    #      查找
        current = self._head
        strs = ''
        while current.next != None:
            current = current.next
            if current.item == item:
                strs = strs + "item:" + str(current.item) + ","
        print(strs)


    def __str__(self):
        return  self.travel()