Linked Lists Overview

Types of Linked Lists

• Singly Linked Lists

  • Structure: Nodes with values pointing to the next node.
  • Example: 1 -> 2 -> 3 -> null
  • Each node has a memory address and points to the next node or null at the end.

• Doubly Linked Lists

  • Structure: Nodes with values pointing to the next and previous nodes.
  • Allows traversal in both directions.

Linked List Node Structure

• A node is an object with:
  • node.value: the value of the node.
  • node.next: a reference to the next node.
  • Memory Address: Each node has a unique address, different from arrays which are contiguous.

Operations on Linked Lists

Adding a Node

• Adding at an arbitrary position:
  • Traverse from the head to the desired position.
  • Update pointers accordingly.
  • Time Complexity: O(n)

Deleting a Node

• Deleting at a specific position:
  • Similar to adding, traverse to the node before the one to delete.
  • Adjust pointers.
  • Time Complexity: O(n)

Accessing a Node

• To access a node's value directly, you must traverse from the head.
• Time Complexity: O(n)

Searching for a Node

• To check for a value, traverse the list to find it.
• Time Complexity: O(n)

Efficient Operations

• O(1) Operations:
  • Removing the head node.
  • Adding a new head node.
  • Requires only updating the head pointer.

Doubly Linked Lists Advantages

• Can delete a node given a reference without traversing the list.
• Requires access to both head and tail nodes for efficiency.

Python Implementation

Singly Linked List Node

• Class: SinglyNode
  • Constructor: Initializes with a value and a next pointer (default is none).
  • Method: __str__ to return string representation of the node.

Creating a Singly Linked List

• Start with a head node, then create other nodes and link them.

Traversing the List

• Use a loop to print values from head to tail.
• Time Complexity: O(n)

Displaying the List

• Function to return a string representation of the list.
• Uses a dynamic array to collect node values and joins them into a string.

Search Function

• Searches for a specific value by traversing the list.
• Returns true or false based on presence.

Doubly Linked List Node

• Class: DoublyNode
  • Constructor initializes value, next, and previous pointers (default is none).

Displaying a Doubly Linked List

• Similar to singly linked but includes both forward and backward traversal display.

Inserting at the Beginning & End

• Insert at Beginning:

  • Create a new node, adjust pointers accordingly.
  • Time Complexity: O(1)

• Insert at End:

  • Create a new node, link it to the tail.
  • Time Complexity: O(1)

Conclusion

• Linked lists provide a dynamic way of storing data.
• Useful in particular scenarios where elements are frequently added or removed.