python---单链表的常用操作

class Node(object):

    """结点"""

    def __init__(self, data):

        self.data = data

        self.next = None

class SingleLinkList(object):

    """单链表"""

    def __init__(self, node=None):

        # 头结点设置为私有变量

        self.__head = node

    def is_empty(self):

        """链表是否为空"""

        return self.__head is None

    def length(self):

        """链表长度"""

        cur = self.__head

        count = 0

        while cur is not None:

            cur = cur.next

            count += 1

        return count

    def travel(self):

        """遍历整个链表"""

        cur = self.__head

        while cur is not None:

            print(cur.data, end="")

            cur = cur.next

        print()

    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

        else:

            cur = self.__head

            while cur.next is not None:

                cur = cur.next

            cur.next = node

    def insert(self, pos, item):

        """指定位置添加结点"""

        # 指定位置pos在第一个元素之前,执行头插法

        if pos <= 0:

            self.add(item)

        # 指定位置超过链表尾部, 执行尾插法

        elif pos > self.length() - 1:

            self.append(item)

        else:

            # 指定位置的前一个结点

            pre = self.__head

            node = Node(item)

            count = 0

            while count < (pos - 1):

                pre = pre.next

                count += 1

            node.next = pre.next

            pre.next = node

    def remove(self, item):

        """删除结点"""

        cur = self.__head

        pre = None

        while cur is not None:

            # 找到了要删除的结点

            if cur.data == item:

                # 要删除的结点是头结点

                if cur == self.__head:

                    # 将头节点指向头结点的后一个结点

                    self.__head = cur.next

                # 要删除的结点不是头结点

                else:

                    pre.next = cur.next

                return

            else:

                pre = cur

                cur = cur.next

    def search(self, item):

        """查找结点是否存在"""

        cur = self.__head

        while cur is not None:

            if cur.data == item:

                return True

            cur = cur.next

        return False

if __name__ == '__main__':

    sll = SingleLinkList()

    print(sll.is_empty())

    print(sll.length())

    sll.append(1)

    sll.append(2)

    sll.append(3)

    sll.append(4)

    sll.append(5)

    sll.travel()   # 12345

    print(sll.length())   # 5

    sll.add(99)           # 99 12345

    sll.travel()

    print(sll.length())   # 6

    print(sll.search(6))  # False

    print(sll.search(4))  # True

    sll.remove(3)

    sll.travel()   # 99 1245
巴特西

python---单链表的常用操作

最新文章

热门文章
