DS – Linked Lists Introduction

How LinkedList different from Array?

Array:

• Array is linear. Array elements get consecutive locations.
• We access array elements easily using index.

Insertions and Deletions taking time – Shifting of elements after insertion and Deletion takes much time.

LinkedList:

• Linked List stores information in the form of nodes.
• Nodes get memory in random locations and connected using links(pointers)

• Insertions and Deletions are faster compared to Array (Array List)
• Inserting and deleting nodes depends on connections.

Array is recommended – if one time store – multiple time accessing data.

LinkedList is recommended – if Multiple times modifying the data.

We have Different types of Linked Lists:

1. Singly linked list
2. Doubly linked list
3. Circular linked list

Singly Linked List:

• Every Node has 2 Fields
  • Data field
  • Link field
• Link Filed is pointer type which store the address of another node
• Data means int, float, structure…….
• Last node link is NULL – No other record to connect.

How to create the node in linked list?

• Node is a memory block with set of fields
• Node fields can be of any type.
• We use structure data type to define the Node.

List representation:

To store Emp data into Linked List node, then Node as follows:

Doubly linked List:

• Every node in double linked list has 3 fields.
  • Data filed
  • Link to previous node
  • Link to next node
• First Node left link and Last Node right link are NULLs

Node representation with structure:

Circular Single Linked List:

• Every node as data filed and link filed in Singly circular linked list
• Last node link is connected to first node.

Node representation:

struct Node             {                         int data;                         struct Node* link;             };

Circular Double Linked List:

• Every node as data filed and 2 link fields
• Last node right link is connected to first node.
• First node left link is connected to the last node.

Node representation:

struct Node             {                         int data;                         struct Node *left, *right;             };