Array
Design of Array
The array design is originally based on memory allocation in form, so space must be requested in advance before use. This gives the array the following characteristics:
1. The size is fixed after the space is requested and cannot be changed (data overflow problem);
2. There is spatial continuity in the memory. , there will be no data that other programs need to call in the middle. This is a dedicated memory space for the array; A lower bound judgment will be made on the operation of the array, and there is a potential risk of out-of-bounds operations (for example, data will be written in the memory of the core part that needs to be called by the running program).
Because simple arrays rely heavily on computer hardware memory, they are not suitable for modern programming. If you want to use variable-size, hardware-independent data types, programming languages such as Java provide more advanced data structures: dynamic arrays such as ArrayList and Vector.
Strictly speaking: There is no array in the strict sense in Python.
List can be said to be an array in Python. The following code is the structure of CPython that implements List:
typedef struct { PyObject_VAR_HEAD /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; /* ob_item contains space for 'allocated' elements. The number * currently in use is ob_size. * Invariants: * 0 <= ob_size <= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 * list.sort() temporarily sets allocated to -1 to detect mutations. * * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it. */ Py_ssize_t allocated; } PyListObject;
Some of the following structures will also be implemented using List.
Stack
What is a stack
Stack (English: stack), also directly called a stack, is a special type of stack in computer science. A data structure in the form of a series. Its special feature is that it can only allow adding data (English: push) and output data (English: top) at one end of the linked series or array (called the top of the stack, English: top). pop) operation. In addition, stacking can also be completed in the form of a one-dimensional array or connected series. Another relative operation mode of stacking is called queuing.
1. First in, first out, last in, first out.
2. Except for the head and tail nodes, each element has a predecessor and a successor.
Operation
It can be seen from the principle that the operations that can be performed on the stack (stack) are:
2. push(): Add an object to the stack
3. pop(): Push an object from the stack
Implementation
class my_stack(object): def __init__(self, value): self.value = value # 前驱 self.before = None # 后继 self.behind = None def __str__(self): return str(self.value) def top(stack): if isinstance(stack, my_stack): if stack.behind is not None: return top(stack.behind) else: return stack def push(stack, ele): push_ele = my_stack(ele) if isinstance(stack, my_stack): stack_top = top(stack) push_ele.before = stack_top push_ele.before.behind = push_ele else: raise Exception('不要乱扔东西进来好么') def pop(stack): if isinstance(stack, my_stack): stack_top = top(stack) if stack_top.before is not None: stack_top.before.behind = None stack_top.behind = None return stack_top else: print('已经是栈顶了')
What is a queue
is similar to a stack, the only difference is that the queue can only be dequeued at the head of the queue. So the queue is a linear table of first-in-first-out (FIFO, First-In-First-Out)
1. First-in-first-out, last-in-last-out
2. Except for the tail node, each node has a successor
3. (Optional) Except for the head node, each node has a predecessor
Operation
1. push():Enqueue
2.pop(): Dequeue
implementation
Ordinary queue
class MyQueue(): def __init__(self, value=None): self.value = value # 前驱 # self.before = None # 后继 self.behind = None def __str__(self): if self.value is not None: return str(self.value) else: return 'None' def create_queue(): """仅有队头""" return MyQueue() def last(queue): if isinstance(queue, MyQueue): if queue.behind is not None: return last(queue.behind) else: return queue def push(queue, ele): if isinstance(queue, MyQueue): last_queue = last(queue) new_queue = MyQueue(ele) last_queue.behind = new_queue def pop(queue): if queue.behind is not None: get_queue = queue.behind queue.behind = queue.behind.behind return get_queue else: print('队列里已经没有元素了') def print_queue(queue): print(queue) if queue.behind is not None: print_queue(queue.behind)
What is a linked list
Linked list is a common basis The data structure is a linear table, but it does not store data in a linear order. Instead, it stores a pointer to the next node in each node. Since it does not have to be stored in order, the linked list can achieve O(1) complexity when inserting, which is much faster than another linear list, sequential list, but finding a node or accessing a specific numbered node requires O(n) time, and the corresponding time complexity of the sequence table is O(logn) and O(1) respectively.
Using the linked list structure can overcome the shortcoming of the array linked list that the data size needs to be known in advance. The linked list structure can make full use of the computer memory space and achieve flexible dynamic memory management. However, the linked list loses the advantage of random reading of the array, and at the same time, the space overhead of the linked list is relatively large due to the increase of the pointer field of the node.
1. init(): initialization
2. insert(): insert
3. trave() : traverse
4. delete() : delete
5. find() : find
implementation
Only two-way lists are implemented here
class LinkedList(): def __init__(self, value=None): self.value = value # 前驱 self.before = None # 后继 self.behind = None def __str__(self): if self.value is not None: return str(self.value) else: return 'None' def init(): return LinkedList('HEAD') def delete(linked_list): if isinstance(linked_list, LinkedList): if linked_list.behind is not None: delete(linked_list.behind) linked_list.behind = None linked_list.before = None linked_list.value = None
The above is all the content of using Python to implement basic linear data structures. I hope this article will help everyone learn Python can help. If you have any questions, you can leave a message to discuss.