When writing algorithms, we often consider using linked lists, but molloc or new space costs too much, often not enough time, at this time we need to use arrays to simulate linked lists.

Singly linked lists

The simplest single linked list

First, set head to -1 and IDx to 0

void init() {
    head = -1;   
    idx = 1;        // The index of node 1 starts at 1
}
Copy the code

Then there is the head insertion method

/** Inserts a number */ to the head of the list
void insert_head(int x) {
    e[idx] = x;/ / assignment
    ne[idx] = head;
    head = idx++;
}
Copy the code

Insert after the KTH number

/** insert a number */ after the position of the first k number
void insert(int k, int x) {
    int temp = k - 1;  // Since we start at 0, actually k-1 is the KTH node
    e[idx] = x;
    ne[idx] = ne[temp];  // set the new pointer to node k+1
    ne[temp] = idx++;
}
Copy the code

Delete the KTH number

/** Delete the number after the KTH number */
void remove(int k) {
    if(! k)// Delete header attributes
        head = ne[head];  // Check if you want to delete the header, yes, the header points to the next point
    else {
        int temp = k - 1;  / / same as abovene[temp] = ne[ne[temp]]; }} to traverse` ``js void print_one() { for (int i = head; i ! = 1; i = ne[i]) cout << e[i] << " "; cout << endl; }Copy the code

sample

Implement a single linked list, the list is initially empty, support three operations:

  1. Insert a number into the list head;
  2. Delete the number after the KTH inserted number;
  3. Insert a number after the KTH number inserted.

Now we’re going to do M operations on the list, and when we’re done, we’re going to print the entire list from beginning to end.

Note: the KTH insertion in the question does not refer to the KTH number in the current list. For example, a total of N numbers are inserted during the operation. The n numbers are the first number inserted, the second number inserted,… The number of NTH insertions.

Input format

The first line contains the integer M, which represents the number of operations.

The following M lines, each line contains an operation command, the operation command may be the following:

  1. H xTo insert a number x into the list header.
  2. D k, means to delete the number after the KTH inserted number (when k is 0, it means to delete the header).
  3. I k x, means that a number x is inserted after the KTH number inserted (k is greater than 0 in this operation).

The output format

In one line, output the entire list from beginning to end.

Data range

1≤M≤100000 All operations are valid.

Example Input:

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
Copy the code

Example output:

6 April 5Copy the code

Simple template problem, the above simulation code can be substituted.

// foreverking#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include  <vector> using namespace std;const int N = 100010;
int value[N],
    nex[N];  // The value array stores the list node, and the next array stores the next node (subscript)
int m, ide, head;  // ide is the current available position, and head is the header pointer, which is the subscript of the header node

/ / initialization
void init() {
    head = -1;
    ide = 0;  // Start from 0
}

/ / head
void insert_head(int x) {
    value[ide] = x;   // The new node is assigned a value
    nex[ide] = head;  // Add the new node to the list from scratch
    head = ide;       // reset the header pointer
    ide++;
}

// Insert after the KTH number
void insert_ca(int k, int x) {
    int temp = k - 1;  // Since we start at 0, actually k-1 is the KTH node
    value[ide] = x;
    nex[ide] = nex[temp];  // set the new pointer to node k+1
    nex[temp] = ide;
    ide++;
}
// Delete the node
void remove(int k) {
    int temp = k - 1;  / / same as above
    nex[temp] = nex[nex[temp]];
}

// Array emulates linked lists
int main() {
    init();  / / initialization
    cin >> m;
    while (m--) {
        char ch;
        int k, x;
        cin >> ch;

        if (ch == 'H') {
            cin >> x;
            insert_head(x);
        } else if (ch == 'D') {
            cin >> k;
            if(! k) head = nex[head];// Check if you want to delete the header, yes, the header points to the next point
            remove(k);
        } else if (ch == 'I') { cin >> k >> x; insert_ca(k, x); }}for(int i = head; i ! = -1; i = nex[i]) cout << value[i] << "";

    cout << endl;
    return 0;
}
Copy the code

Double linked list