How LinkedList different from 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.
- 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:
- Singly linked list
- Doubly linked list
- 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.
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.
| struct Node|
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.
| struct Node|
struct Node *left, *right;