Nikhil Kumar SinghVrishchik

There are two well-known types of linked lists; the singly linked list and the doubly linked list. In a singly linked list, we’ve got a linear structure with every node having one next pointer to maneuver forward, whereas in a doubly-linked list we have the same structure but each node also incorporates a previous pointer to maneuver backward. Below is the structure of both types of linked lists:

```
1
2
3
4
5
6
7
8
9
10
```

```
struct SinglyListNode {
int val;
SinglyListNode * next;
};
struct DoublyListNode {
int data;
DoublyListNode * next;
DoublyListNode * prev;
};
```

In this article, we will define one more type of linked list which solves the O(n) linear complexity of insertion and search into a linked list to about O(√n).

An unrolled linked list is a variation of a linked list where one block contains a circular linked list of its own. If there are n elements in an unrolled linked list then all blocks except the last one should contain ⌈√n⌉ nodes.

Structure of an unrolled linked list:

```
1
2
3
4
5
```

```
struct UnrolledLinkedBlock {
LinkedBlock * next;
SinglyListNode * head;
int count;
};
```

Below you can see an unrolled linked list representation with twelve nodes and each block containing four nodes:

One important aspect when inserting into an unrolled linked list is maintaining its ⌈√n⌉ nodes per block property as it helps to search and perform other operations optimally.

**Algorithm:**

Insert a node at X after the ith node in the kth block.

Now to maintain the ⌈√n⌉ property, shift the nodes in the block, current, and next blocks towards the tail.

Make sure every block has exactly ⌈√n⌉ nodes.

If one node exceeds the ⌈√n⌉ space add one more block.

The node below with value twenty-five is inserted in the first block and now we shift node thirty-seven to the next block. Doing this maintains the ⌈√n⌉ property.

Here we will use the ⌈√n⌉ property to skip some blocks and search optimally.

**Algorithm:**

To search a kth element traverse the blocks to one containing kth block, that would be the ⌈k/√n⌉th block.

It will take a maximum of √n blocks.

Now in this block access the k%⌈√n⌉ th node in the circular linked list.

The above also takes a maximum of ⌈√n⌉ nodes.

Now let’s search the seventh node in our list below:

We first move to the ⌈7/4⌉th block, i.e first block, and access the ⌈7%4⌉th block, i.e third node, and you will find it.

```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
```

```
#include<bits/stdc++.h>
using namespace std;
int size;
struct ListNode {
ListNode * next;
int value;
ListNode(int val) {
this - > next = NULL;
this - > value = val;
}
};
struct LinkedBlock {
LinkedBlock * next;
ListNode * head;
int nodeCount;
LinkedBlock() {
this - > next = NULL;
this - > head = NULL;
this - > nodeCount = 0;
}
};
LinkedBlock * blockHead;
void searchElement(int k, LinkedBlock ** block, ListNode ** node) {
int j = (k + size - 1) / size;
LinkedBlock * p = blockHead;
while (--j)
p = p - > next;
* block = p;
ListNode * q = p - > head;
k = k % size;
if (!k) k = size;
k = p - > nodeCount + 1 - k;
while (k--)
q = q - > next;
* node = q;
}
void shift(LinkedBlock * A) {
LinkedBlock * B;
ListNode * temp;
while (A - > nodeCount > size) {
if (A - > next == NULL) {
A - > next = new LinkedBlock();
B = A - > next;
temp = A - > head - > next;
A - > head - > next = A - > head - > next - > next;
B - > head = temp;
temp - > next = temp;
A - > nodeCount--;
B - > nodeCount++;
} else {
B = A - > next;
temp = A - > head - > next;
A - > head - > next = A - > head - > next - > next;
temp - > next = B - > head - > next;
B - > head - > next = temp;
B - > head = temp;
A - > nodeCount--;
B - > nodeCount++;
}
A = B;
}
}
void addElement(int k, int x) {
ListNode * p, * q;
LinkedBlock * r;
if (!blockHead) {
blockHead = new LinkedBlock();
blockHead - > head = new ListNode(x);
blockHead - > head - > next = blockHead - > head;
blockHead - > nodeCount++;
} else {
if (k == 0) {
p = blockHead - > head;
q = p - > next;
p - > next = new ListNode(x);
p - > next - > next = q;
blockHead - > head = p - > next;
blockHead - > nodeCount++;
shift(blockHead);
} else {
searchElement(k, & r, & p);
q = p;
while (q - > next != p) q = q - > next;
q - > next = new ListNode(x);
q - > next - > next = p;
r - > nodeCount++;
shift(r);
}
}
}
int searchElement(int k) {
ListNode * p;
LinkedBlock * q;
searchElement(k, & q, & p);
return p - > value;
}
void display() {
ListNode * p;
LinkedBlock * q = blockHead;
int list = 0;
while (q != NULL) {
p = q - > head;
cout << "Block " << list << ": ";
list++;
cout << p - > value << "<--";
p = p - > next;
while (p != q - > head) {
if (p - > next != q - > head)
cout << p - > value << "<--";
else
cout << p - > value;
p = p - > next;
}
q = q - > next;
cout << endl;
}
}
int main() {
int m, i, k, x;
string type;
cin >> m;
size = (int)(sqrt(m - 0.001)) + 1;
for (int i = 0; i < m; i++) {
cin >> type;
if (type == "add") {
cin >> k >> x;
addElement(k, x);
} else {
cin >> k;
cout << searchElement(k) << endl;
}
}
display();
}
```

**Input:**

12

add 0 2

add 0 7

add 0 8

add 0 9

add 2 17

add 0 5

add 0 3

add 0 6

search 5

search 1

search 6

search 7

**Output:**

8

6

17

7

Block 0: 6<–9<–5<–3

Block 1: 8<–2<–7<–17

We can improve our structure above by replacing the linked list with an array of size ⌈√n⌉, this makes the implementation easier.

#define size 4

struct UnrolledLinkedBlock{

LinkedBlock *next;

int nodes[size];

int count;

};

**Insertion:** O(⌈√n⌉), we have only ⌈√n⌉ blocks and ⌈√n⌉ nodes per block so a maximum of ⌈√n⌉ is traversed before adding.

**Shifting:** O(⌈√n⌉), shift operation included when we add or remove a node from the tail of the circular linked list which takes only O(1) and a maximum of O(⌈√n⌉) shift operation, as only one shift is required per block.

**Searching:** O(⌈√n⌉), we have only ⌈√n⌉ blocks and ⌈√n⌉ nodes per block so a maximum of ⌈√n⌉ are required before we find our element.

**Advantages:**

Operations like insertion, deletion, and searching are faster than a linked list.

Compared to the original linked list it requires less space for a pointer.

Provides faster performance when we consider cache management.

**Disadvantages:**

Unlike the original linked list, overhead per node is quite high in an unrolled linked list.

Discuss this article in the forums
Binary search is one of the fundamental algorithms in computer science. I...

Read More What is LRU Cache?
Least Recently Used (LRU) is a cache replacement algorithm that replaces cache
when the spa...

Read More About the Problem:
In this problem, we are provided with the root of the binary tree and we should
use the sam...

Read More