Python implements basic linear data structures

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.

Arrays in Python

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;

Of course, it is an array in Python.

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.

Since the stacked data structure only allows operations on one end, it operates according to the principle of LIFO (Last In First Out).

Features

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:

1. top(): Get the top object of the stack

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('已经是栈顶了')

Queue

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)

Features

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)

Linked list

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.

Features

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.

Operation

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

Summary

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.

For more articles related to Python’s implementation of basic linear data structures, please pay attention to the PHP Chinese website!