5.1.11 – 5.113 – Linked Lists
Linked list is a dynamic data structure whose length can be increased or decreased at run time.
How Linked lists are different from arrays? :
- An array is a static data structure. This means the length of array cannot be altered at run time. While, a linked list is a dynamic data structure.
- In an array, all the elements are kept at consecutive memory locations while in a linked list the elements (or nodes) may be kept at any location but still connected to each other.
- Linked list basically consists of memory blocks that are located at random memory locations and are connected through pointers
When to prefer linked lists over arrays?
Linked lists are preferred mostly when you don’t know the volume of data to be stored.
Basically, there are three types of linked list,
- In a singly-linked list every element contains some data and a link to the next element
- In a doubly-linked list also contains a link to the previous node.
- In a Circular Link List the last element points to the first element
In programming or computing a Node is considered a basic object or element.
For a linked lists a node contains both data and a pointer
A pointer is a field of the nose that points to another object or node (in a different memory location
Each node in a linked list stores a point to the next node/value of the linked list
This means each node needs memory for its data and its pointer.
The Null pointer a special pointer that points to nothing at all.
The NULL point is drawn as the following:
Or written as NULL
Inserting into a Linked List
Head and Tails
The head node is the first node in the list.
- Insert new node before the start of the head node and the new node becomes the head node
The tail node is, where the next pointer is always pointing or linking to a null reference, indicating the end of the list.
- If a node is inserted after the tail node the new node becomes the tail node