- It is a linear data structure.
- In linear data structure one element is connected to only one element.
Differentiate Arrays from Linked Lists?
- 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 compare to Array (Array List)
- Inserting and deleting nodes depends on connections.
- In My application, we insert the records only once and process (access) every time. Array List is recommended.
- We use linked lists when our application requires continuous insertions and deletions of records.
We have Different types of Linked Lists:
- Singly linked list
- Doubly linked list
- Circular linked list
Singly Linked List:
Node has 2 Fields
- Data field
- Link field
- Link Filed is pointer type
- Data means int, float, structure…….
- Last node link is NULL – No other record to connect.
- We represent the node with structure type as follows.
- Structure is used to represent different data types set.
- Node has 2 fields representing data and link of different types as follows.
To store Emp data into Linked List node, then Node as follows:
- In the above diagram, we take data as int type.
- We can store records information like Employee details, Student details, Account details…
- We can represent the data field as multiple fields to store records information.
- The following diagram represents a node that stores Employee details and link to next node.
Doubly linked List:
- Doubly linked list is also called Bi-directional linked list.
- We can process the information either in forward direction as well as in backward direction.
- Every node has 2 pointers pointing to next node and previous node.
- Every node contains 3 fields.
- Data filed
- Link to previous node
- Link to next node
- First Node left link is NULL
- Last Node right link is NULL
Circular Linked List:
- Every node as data filed and link filed in Singly circular linked list
- Last node link is connected to first node.
- We can implement circular linked list in 2 ways.
- Using singly linked list
- Using doubly linked list
- The following diagram represents circular singly linked list in which the last node link is pointing to root node in the list.
Circular double linked list:
- In Circular doubly linked list:
- Last node connects to first node
- First node is connected to last node.
- The following diagrams shows how the structure will be