4: Singly (Simply) Linked Lists

Singly (Simply) Linked Lists
List
List is a set of items or elements, list can be:
- Non-linked List: such type is implemented using arrays, the locations of non-linked don t need to link because they are sequential in RAM.
- Linked List: such type needs pointers for implementing it, pointer does as linker between the non-sequential locations.
Linked Lists
In order to avoid the linear cost of insertion and deletion, we need to ensure that the list is not stored contiguously, since otherwise entire parts of the list will need to be moved. A linked list, in its simplest form, is a collection of nodes that together form a linear ordering.
Linked Lists are a very common way of storing arrays of data. The major benefit of linked lists is that you do not specify a fixed size for your list. The more elements you add to the chain, the bigger the chain gets.
The linked list consists of a series of nodes, which are not necessarily adjacent in memory. Each node contains the element and a link to a node containing its successor. We call this the next link. The last cell’s next link references null.
There is more than one type of a linked list, we ll stick to singly linked lists (the simplest one). If for example you want a doubly linked list instead, very few simple modifications will give you what you re looking for. Many data structures (e.g. Stacks, Queues, Binary Trees) are often implemented using the concept of linked lists.