Linked List Fundamentals

Linked List Fundamentals

• A linked list is a data structure for storing a collection of data in which each element is an independent object known as a node.
• Each node consists of two key components:
  • Data Field: Contains the value of the element.
  • Pointer Field: Holds the address of the next node, known as the successor.
• The first node is designated as the head, while the last node's pointer points to null, indicating the end of the list.

Visual Representation of Linked Lists

• Nodes are illustrated with the following characteristics:
  • The address of the node is placed above its data field.
  • The pointer field shows the address of the next node.
  • The last node’s pointer field indicates null.
  • Arrows connect consecutive nodes, illustrating the link between them.

Linked List Operations

• Display: Outputs the elements present in the list.
• Insert: Facilitates the addition of a new element to the list.
• Delete: Removes a specified element or all elements from the list.
• Search: Locates a specific element within the list.
• Count: Returns the total number of elements in the list.

Comparison: Linked List vs. Array

• Element Flexibility:
  • Linked lists can grow or shrink dynamically; arrays have a fixed size determined at creation.
• Memory Allocation:
  • Linked lists allocate memory at runtime, while arrays allocate memory at compile time.
• Element Access:
  • Linked lists allow sequential access, contrasting with arrays which permit random access.
• Memory Efficiency:
  • Linked lists typically utilize memory more efficiently than arrays due to their dynamic nature.

Types of Linked Lists

• Singly Linked List: The simplest form of a linked list with one pointer per node.
• Doubly Linked List:
  • Contains two pointers per node:
    • Left Pointer: Connects to the preceding (previous) node.
    • Right Pointer: Points to the next node in the sequence.
  • Visual includes:
    • The left pointer field contains the address of the predecessor.
    • The right pointer field holds the address of the successor.
    • Null is indicated in the left pointer of the first node and right pointer of the last node.

Circular Linked List

• A variation where the last node's right pointer references the first node, forming a circle, allowing for continuous traversal of the list.