Wednesday, August 31, 2016

linked list are not stored in adjacent memory locations as in array

Imagine that your computer has a 16 bit memory which is initially nil, like follow

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

0 represents the free spaces
1 represents the occupied spaces
* represents the filed spaces

If you define a array with 5 elements whare 1 element takes 1 bit of memory it will allocate the memory as follow.

|  1  |  1  |  1  |  1  |

|  1  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

When you fill the array with first elements it will fill the 0th allocation

| * | 1 | 1 | 1 |

| 1 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

and when its second

| * | * | 1 | 1 |

| 1 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

But if you define an linked list for the same perpose, allocation is one at the initiation. That allocation is for the details of "Where to start".

| 1 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

When you fill the first element it uses the allocated space as follow. Additionaly it allocates a free space for next element

| * | 1 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 |

Then we can add second element

|  *  |  *  |  1 |  0  |

|  0  |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

Think that while we adding the 3rd element 4th and 5th location were allocated by a nother process.

We use x for the locations allocated by third party

|  *  |  *  |  1  |  X |

|  X |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

|  0  |  0  |  0  |  0 |

No Problem with that ... When we fill the 3rd element it will allocate 5th space for the 4th element of array list as follow


|  *  |  *  |  *  |  X |

|  X |  1  |  0  |  0  |

|  0  |  0  |  0  |  0  |

|  0  |  0  |  0  |  0  |

This is ok becase linked list keeps the location of next element as metadata..

As you see in Linked list we don't need any order for memory allocation. so we can say that  linked list are not stored in adjacent memory locations as in array.

No comments:

Post a Comment