Java

TOPIC 25 – IMPLEMENTING A LINKED LIST

LESSON NOTE

LINKED LISTS

A linked list is a collection of elements that can be sequentially accessed. So if you want the 5^th element, you have to go to the 1^st element, then to the next, then to the next, then to the next and finally once more to the next element.

Linked lists can be created by using OOP concepts where each element is a Node that contains its data and a link to the next element.

A linked list is a grouping of objects called nodes. Each node stores one piece of data and the location of the next node. Nodes do not have to be stored together in memory.

ARRAYS vs LINKED LISTS

Arrays have the advantage that they allow direct access to any element. Linked lists do not. To reach the 100^th element, you have to go through the first 99.

Arrays also require less storage space as linked lists store both data and an address to the next element.

Linked lists have a considerable advantage when inserting and removing elements. This simply requires a few simple adjustments to the links between elements. In an array, in the very least, either inserting or deleting elements will lead to shifting of elements (sometimes lots of elements) from one cell to the next one over.