5.1.11 – 5.1.13 – Linked lists

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,

Singly-Linked List

  • In a singly-linked list every element contains some data and a link to the next element

Doubly-Linked List

  • In a doubly-linked list also contains a link to the previous node.

Circular-Linked List.

  • In a Circular Link List the last element points to the first element

Nodes

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.

Image result for linked list node pointer data

Null Pointers

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

Image result for head and tail nodes linked list

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