List Linked through Nodes

Introduction to linked lists

We’ve seen that the two most natural ways of storing sequences in computer memory are arrays and linked lists. ArrayList is an ADT that uses all concepts of handling arrays more flexibly. That is why the time complexity is the same for arrays and linked lists.

Linked lists don’t work that way. We usually model the memory as a sequence of memory cells, each of which has a unique address. An array or an ArrayList is a contiguous piece of memory. Each cell of the memory stores one object, which is a part of the sequence stored in an array or an ArrayList.

In a singly linked list, two successive memory cells are allocated for each object of the sequence. Two memory cells form a node of a sequence. The first cell stores the value of the object, and the second cell stores a reference to the next node of the list.