Data Structures: Linked Lists
Linked lists are extendable collections. Unlike an array, once a linked list has been created the elements can easily be added and removed while remaining memory efficient, ie the size of the list is flexible.
This is accomplished by each element having a reference to the next, therefore other elements can live anywhere in memory. The below linked list does not allocate memory for the maximum size of the list, you can simply add new items on.
A disadvantage of linked lists is that they are slow to search. This is because every element needs to be checked by following the chain of links. ie cant simply go to an index because the collection is not in predefined memory locations.
Linked List Example in memory
element 1: memory 100 and points to 264
element 2: memory 264 and points to 345
element 3: memory 345 and points to 569
element 4: memory 569 and points to null
This structure makes it harder to find elements because you have to traverse through each element.
Goto 1st element at 100 and find out where 2nd element is (264) =>
Goto 2nd element at 264 and find out where 3rd element is (345) =>
Goto 3rd element at 345 and find out where 4th element is (569) =>
Goto 4th element at 569
The benefit of this structure is that you can keep adding more references onto the end and extend the size of the linked list.