This is the 8th day of my participation in the August More Text Challenge

Zero foreword

Why use arrays to simulate linked lists when you have ready-made ones?

The reason: You create your own memory pool, avoiding memory leaks and facilitating debugging. More specifically, arrays are stored centrally, which improves Cache hit ratios.

Of course, the most important reason is efficiency. Most of the data in the algorithm is 100,000 to million level, if you use the new method, it is easy to TL is timeout.

Therefore, it is very important to master the method of simulating linked lists with arrays. This article mainly describes the simulation of single and double linked lists.

Note: this article is C++ implementation, but all languages common, will omit part of the implementation irrelevant code. Will skip some basic concepts, do not understand Baidu can, we directly look at the implementation ❤

A singly linked list

implementation

We use e and NE arrays to store data and Pointers, respectively, while initializing head and IDX.

const int N = 100010;// Define constants

// e[I] represents the value of node I
// ne[I] indicates the next pointer to node I
// head indicates the subscript of the head node, starting with -1
// idx stores which node is currently used
intE [N], NE [N], head =- 1, idx;	
Copy the code

Then we implement the basic operations insert and delete:

// Insert x into the header
void insert_head(int x) {
    e[idx] = x;
    ne[idx] = head;	// 1. Point x to the original header
    head = idx;		// 2. X is the new header
    idx++;
}

Insert x after the number of the KTH insert, k starting at 0 (same below)
// Let the x term point to the next k term, and let the k term point to the x term
void insert(int k, int x) {e[idx] = x, ne[idx] = ne[k], ne[k] = idx++; }// Delete the KTH insert
void remove(int k) {
    ne[k] = ne[ne[k]];	// Directly points to the item after the item
}
Copy the code

As you’ve probably noticed, when we delete a node, we don’t use any of the items we used. The nice thing about this is that we don’t have to spend any time managing memory, we just have to make the array a little bigger, and it’s a lot faster, because the array is O(1) random access. At the same time, NULL is replaced by -1, regardless of NULL pointer exceptions.

/ / traverse
for (inti = head; i ! =- 1; i = ne[i]) {
     cout << e[i] << ' ';
}
Copy the code

application

1. Multiple singly linked lists (adjacency lists) are often used to store trees and graphs. A tree is a special graph that is stored in the same way as a graph.

   For the edge AB of an undirected graph, we store two directed edges A -> B and b-> A, so we only consider the storage of directed graphs:

   // For each point k, a single linked list is built to store all possible points.
   // h[k] stores the header of each singly linked list
   int h[N], e[N], ne[N], idx;
   
   / / initialization
   memset(h, - 1.sizeof h);
   
   // Add an edge a->b
   void add(int a, int b) {
       e[idx] = b, ne[idx] = h[a], h[a] = idx++；
   }
   Copy the code

2. Hash table zipper method

   // h[k] stores the header of each singly linked list
   int h[N], e[N], ne[N], idx;
   memset(h, - 1.sizeof h);
   
   // insert x into the hash table
   void insert(int x) {
       int k = (x % N + N) % N;
       / / head
       e[idx] = x, ne[idx] = h[k], h[k] = idx++;
   } 
   
   // find if x is in the hash table
   int find(int x) {
       int k = (x % N + N) % N;
       // go through the search
       for (inti = h[k]; i ! =- 1; i = ne[i])
           if (e[i] == x)
               return true;
       return false;
   }
   Copy the code

Two double linked list

implementation

Use l and R arrays to store the left and right Pointers respectively, with 0 as the left endpoint, 1 as the right endpoint, and IDx starting at 2:

const int N = 100010;
int e[N], l[N], r[N], idx;

/ / initialization
void init(a) {
    r[0] = 1, l[1] = 0;
    idx = 2;
}
Copy the code

Similar to single-linked list insertion and deletion, we only need to pay attention to the pointing order of the two Pointers:

// Insert x to the right of the KTH insert
void insert(int k, int x) {
    e[idx] = x;
    l[idx] = k, r[idx] = r[k];	// 1. Set the left and right Pointers of x to the node pointed to by k and k respectively
    l[r[k]] = idx;		// the left pointer to the node 2. K points back to x
    r[k] = idx;			// 3. The right pointer to k points to x
    idx++;
    
    // Can be omitted as a single list with a comma
}

// delete the KTH item
void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];		// Two sentences can be reversed order, will not break the chain
}
Copy the code

Unlike a singly linked list, we implement a single insert that implements head, tail, left, and right inserts:

// Insert the number x at the left end of the list
insert(0, x);
// Insert x at the right end of the list
insert(l[1], x);
// the number of left insertions x
insert(l[k], x);
// insert x to the right of k
insert(k, x);
    
// traversal, note that I should start from r[0]
for (int i = r[0]; i ! =1; i = r[i]) {
    cout << e[i] << ' ';
}
Copy the code

Three summary

This idea is mainly from AcWing. After reading it, you can find a template to practice.

Grasp the array simulation linked list method, dynamic linked list with class implementation call function naturally can easily master.

The most obvious advantage of linked lists is that they allow nodes to be inserted and deleted at any location on the table, while the disadvantage is that they do not allow random access.

In fact, a linked list is just like an array, except that their index values are different. An array is an ordered index, while a linked list is connected by address values. So we can think of it as an array, except that the index values are handled differently.

All see here, click a like bai (crazy hint) 😆

Have any question can comment message ~ can pay attention to each other exchange

More interesting articles: Mancuoj’s homepage – Articles – Nuggets (juejin. Cn)