Linked List Data Structure

A linked list is a fundamental data structure in computer science. It primarily enables efficient addition and deletion operations compared to arrays. Arrays are also used to implement other data structures such as like, stack, queue, and deque.

Data Structure: Non-contiguous

Memory Allocation: Typically allocated individually for each element

Insertion/Deletion: Efficient

Access: Sequential

Singly Linked List

A singly linked list is a basic data structure composed of nodes, each containing a data field and a reference to the next node in the linked list. The next field of the last node is null, indicating the end of the list. Linked lists support active insertion and deletion operations.

Node Structure

In a singly linked list, each knot consists of two parts: data and a pointer to the next node. This building allows nodes to be linked together and form a structure similar to an array opportunity.

Singly Linked List Operations

• Traversal - Listing
• Search
• Length Calculation
• Insertion
• • Insert at beginning
  • Insert at end
  • Insert at a specific position
• Deletion
• • Delete from beginning
  • Delete from end
  • Delete a specific node

Java Implementation of Traversal:

Java Implementation of Search:

Java Implementation of Length Calculation:

Java Implementation of Insertion:

Java Implementation of Deletion:

Doubly Linked List

A doubly linked list is a data structure consisting of a sequence of nodes, each containing a value and two pointers: one pointing to the previous node and another pointing to the next node in the list. This enables efficient traversal in both directions, making it suitable for applications requiring frequent insertion and deletion operations.

In a data structure, a doubly linked list is represented using nodes with three fields:

• Data
• A pointer to the next node (next)
• A pointer to the previous node (prev)

Java Implementation of Length Calculation:

Java Implementation of Insertion:

Java Implementation of Deletion: