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.