Advanced Data Structure : Easy Explanation

1. Unrolled Linked List :

A simple linked list look like this,

A single node consists Value and Reference of next Node

But an Unrolled Linked list will look like this,

A single node consist array of Values and a Reference to next Array Node

2. Skip List :

A sorted link list look like this :

Sorted link list

Time complexity of search in a sorted linked list : O(n)

A Skip list (It’s an improvement only to a sorted linked list) would look like this :

In Skip link list, few nodes have reference of a distant node at K distance along with its immediate node.

Advantage : While traversing Node 0, will check if distant node reference of Node 0 that is Node 3’s value is less than the value which we are searching or more than that, if lesser, then we will move to check the distant node of Node 3 i.e. Node 6.

Now let’s say distant node of Node 6 i.e. Node 9 is greater than the target value, then we will check between Node 6 and Node 9 using immediate node.

3. Self Organising List :

It is an improvement to a simple linked list to make the search better. It try to reshuffle the linked list based on the access, the more frequent the access is, Node would be shifted to near Head position.

By this reorganisation, it will reduce the search time for the most frequent items. There are 3 ways of Self organisation.

a) Whenever node is accessed, move it to the head.

b) Whenever a node is accessed then move it by one position to its left.

c) Whenever node is accessed, it should be reordered based on the frequency. (Please refer the original diagram where we understood Self Organised list)

4. XOR Linked List :

XOR linked list is an improvement over doubly linked list.

A doubly linked list need to keep 2 references, one for next node and another for previous node and that’s how it is able to move forward and backward. Problem with this approach it consumes more memory. To solve the same, XOR linked list uses a single reference in which it stores the XOR of next and previous nodes.

Before understanding the way how we traverse into a XOR linked list, it should be known to us that how XOR (^) operation works,

Node 5's npx stores XOR of previous and next nodes, i.e. 2 ^ 7

If want to move forward then we will take XOR of 2 ^ 7 with the previous node of Node 5 i.e. Node 2 as,

2^ (2 ^ 7) = 7. (It will cancel out the node 2 and in the result we would get Node 7, so we do now have reference of next node i.e. node 7 and we can move forward)

Similarly to move backward, we can take XOR of npx value of Node 5 with its next node to move backward i.e. (2 ^ 7) ^ 7 = 2 (will get previous node this way)

Hope we understood now that How XOR operation helps into moving forward and backward, so to traverse the XOR linked list, we would have a PREV node with value null, if taken XOR of this with npx value of Node 2, it will give Node 5 reference and we will move forward.

Now replace PREV node with Node 2 and taking the XOR operation with Node 5 and so on, That’s how we will traverse the complete linked list.

5. Trie :

A Binary search tree has maximum 2 children but a Trie Node can have multiple nodes as children. Structure of a standard Trie is as below.

In the above tree structure, we tried to implement a word dictionary, where a Node is composed of,

a) a char value

b) a alphabet array for next possible word reference

c) a Integer value to mark if it makes a complete word or not

To search a word into above designed dictionary, it will take O(n) time where n is the length of the word.