After learning about the chained storage structure of linear lists, someone came up with the idea of using arrays instead of Pointers to describe singly linked lists. Let’s see how they did it.

A static linked list

Let the elements of the array consist of two data fields, data and CUR. That is, each index of the array has a corresponding data and cur. The data field, data, is used to store data elements, and cur is the equivalent of the next pointer in a single linked list, which stores the index of the element’s successors in the array. We call cur a cursor.

This array representation of a list is called a static list, and we call this representation a cursor implementation.

In addition, we treat the first and last elements of the array as special elements and store no data. Unused array elements are often referred to as standby lists.

The cur of the first element of the array, which is 0, is the index of the first node of the standby list; The cur element at the end of the array holds the index of the first numeric element, acting as a head node in a single-linked list.

The diagram below:

Insert and delete static lists

Static linked list to solve is: how to use static simulation dynamic linked list storage space allocation, when the need to apply, useless release.

Insertion of static linked lists

Static list deletion

Advantages and disadvantages of static linked lists

  • During insert and delete operations, only cursors need to be modified, and no elements need to be moved, thus improving the disadvantage of insert and delete operations in sequential storage structures that require a large number of elements to be moved.
  • It does not solve the problem of indeterminate table length caused by continuous memory allocation.
  • Random access features of sequential storage structures are lost.

Circular linked list

For a single linked list, since each node stores only the backward pointer, the backward chain operation is stopped at the end of the list, so that when a node cannot find its precursor node.

Changing the pointer end of the terminal node in a single linked list to point to the head node instead of the null pointer will make the whole single linked list form a ring. This kind of single linked list is called single circular linked list, or circular linked list for short.

This obviously solves a problem: when you start at one node, access all nodes of the linked list.

Two-way linked list

Bidirectional linked list: in each node of a single linked list, a pointer field is set to point to its precursor node.

Advantages of bidirectional linked lists: a node can operate on the front and back nodes faster;

Disadvantages of bidirectional linked lists: one node, two Pointers, more memory consumption.

Since a singly linked list can be a circular list, a bidirectionally linked list can also be a circular list, with the following structure:

Insertion of bidirectional linked lists

Removal of bidirectional linked lists

This is the end of the linear list. If there are any inadequacies or shortcomings in the article, I hope you can give me feedback and make progress together.

More exciting content, pay attention to my wechat public number – Android motor vehicle