How to implement the data structure of Python's underlying technology

How to implement the data structure of Python's underlying technology

Data structure is a very important part of computer science. It is used to organize and store data so that it can be operated efficiently and access data. As a high-level programming language, Python provides a wealth of built-in data structures, such as lists, tuples, dictionaries, etc., but sometimes we also need to implement some underlying data structures to meet specific needs.

This article will introduce how to use Python to implement several common underlying data structures, including stacks, queues, and linked lists, and provide corresponding code examples.

1. Stack

The stack is a last-in-first-out (LIFO) data structure that only allows insertion (push) and deletion (pop) at the top of the stack )operate. In Python, you can use lists to implement a simple stack.

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

Use the Stack class to create a stack object and perform operations:

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.size())    # 输出：3
print(stack.pop())     # 输出：3
print(stack.peek())    # 输出：2
print(stack.is_empty())     # 输出：False

2. Queue (Queue)

The queue is a first-in-first-out ( The data structure of FIFO only allows insertion (enqueue) operations at the end of the queue and dequeue operations at the head of the queue. You can use lists to implement a simple queue in Python.

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def size(self):
        return len(self.items)

Use the Queue class to create a queue object and perform operations:

queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
print(queue.size())    # 输出：3
print(queue.dequeue())     # 输出：'a'
print(queue.is_empty())    # 输出：False

3. Linked List

The linked list is a dynamic data structure , consists of a series of nodes, each node contains two parts: data and a pointer to the next node. In Python, you can use classes to implement a simple linked list.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add_node(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node

    def remove_node(self, data):
        if not self.is_empty():
            current_node = self.head
            if current_node.data == data:
                self.head = current_node.next
            else:
                while current_node.next:
                    if current_node.next.data == data:
                        current_node.next = current_node.next.next
                        break
                    current_node = current_node.next

    def get_size(self):
        size = 0
        current_node = self.head
        while current_node:
            size += 1
            current_node = current_node.next
        return size

Use the LinkedList class to create a linked list object and perform operations:

linked_list = LinkedList()
print(linked_list.is_empty())    # 输出：True

linked_list.add_node(1)
linked_list.add_node(2)
linked_list.add_node(3)
print(linked_list.get_size())    # 输出：3

linked_list.remove_node(2)
print(linked_list.get_size())    # 输出：2

Through the above code examples, we demonstrate how to use Python to implement common underlying data such as stacks, queues, and linked lists. structure. These data structures are widely used in algorithms and data processing. Mastering their implementation principles and usage methods is very important to further improve programming abilities.

The above is the detailed content of How to implement the data structure of Python's underlying technology. For more information, please follow other related articles on the PHP Chinese website!