

Linked List

It is not hard to find that the block linked list is a linked list, and each node points to an array. We divide the original array of length n into nodes, and the size of the array corresponding to each node is . So we define the structure as the code below shows. Among them, sqn means sqrt(n) that is , and pb means push_back, that is, adding an element to this node.

struct node {
  node* nxt;
  int size;
  char d[(sqn << 1) + 5];
  node() { size = 0, nxt = NULL, memset(d, 0, sizeof(d)); }
  void pb(char c) { d[size++] = c; }
};

Block linked lists should at least support these operations: split, insert, and lookup. What is split? It is to split a node into two small nodes to ensure that the size of each node is close to (otherwise it may degenerate into an ordinary array). When the size of a node exceeds , the split operation is performed.

How to do the split operation? First create a new node, and then copy the last values of the split node to the new node, and then delete the last values of the split node (size-- ), and finally insert the new node after the node being splited.

The time complexity of all operations of the block linked list is .

There is one more thing worth mentioning here.

As elements are inserted (or deleted), will change, and will also change. In this way, the size of the block will change. Do we have to maintain the size of the block every time?

In fact, this is not the case. we could just set to a fixed value. For example, the range given by the title is , then is set as a constant with a size of , so we don't need to change it.

list<vector<char> > orz_list;

Sample problem¶

Big String POJ - 2887

Solution: This is a very simple template problem. The code is shown below:

#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;
static const int sqn = 1e3;
struct node {
  node* nxt;
  int size;
  char d[(sqn << 1) + 5];
  node() { size = 0, nxt = NULL; }
  void pb(char c) { d[size++] = c; }
}* head = NULL;
char inits[(int)1e6 + 5];
int llen, q;
void readch(char& ch) {
  do
    ch = getchar();
  while (!isalpha(ch));
}
void check(node* p) {
  if (p->size >= (sqn << 1)) {
    node* q = new node;
    for (int i = sqn; i < p->size; i++) q->pb(p->d[i]);
    p->size = sqn, q->nxt = p->nxt, p->nxt = q;
  }
}
void insert(char c, int pos) {
  node* p = head;
  int tot, cnt;
  if (pos > llen++) {
    while (p->nxt != NULL) p = p->nxt;
    p->pb(c), check(p);
    return;
  }
  for (tot = head->size; p != NULL && tot < pos; p = p->nxt, tot += p->size)
    ;
  tot -= p->size, cnt = pos - tot - 1;
  for (int i = p->size - 1; i >= cnt; i--) p->d[i + 1] = p->d[i];
  p->d[cnt] = c, p->size++;
  check(p);
}
char query(int pos) {
  node* p;
  int tot, cnt;
  for (p = head, tot = head->size; p != NULL && tot < pos;
       p = p->nxt, tot += p->size)
    ;
  tot -= p->size;
  return p->d[pos - tot - 1];
}
int main() {
  scanf("%s %d", inits, &q), llen = strlen(inits);
  node* p = new node;
  head = p;
  for (int i = 0; i < llen; i++) {
    if (i % sqn == 0 && i) p->nxt = new node, p = p->nxt;
    p->pb(inits[i]);
  }
  char a;
  int k;
  while (q--) {
    readch(a);
    if (a == 'Q')
      scanf("%d", &k), printf("%c\n", query(k));
    else
      readch(a), scanf("%d", &k), insert(a, k);
  }
  return 0;
}

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article HeRaNO, konnyakuxzy
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Linked List

Sample problem¶

Comments