1 of 25

Linked Lists

Unit 5 - Abstract Data Structures

2 of 25

Types of Linked Lists

​

  • Singly Linked Lists - each node has a pointer to the next node
  • Doubly Linked Lists - each node has a pointer to the next and previous nodes
  • Circular Linked Lists - last node points to the first node

3 of 25

Introduction to Linked Lists

  • Linear data structure that stores elements in non-contiguous memory locations
  • Composed of nodes that contain data and a pointer to the next node

4 of 25

Singly Linked List

5 of 25

Singly Linked List (with data)

6 of 25

Singly Linked List

​

  • Advantages
    • Simpler implementation compared to doubly linked lists
    • Efficient for insertion and deletion at head and tail
  • Disadvantages
    • Traversal requires O(n) time
    • No efficient way to traverse backwards

7 of 25

Doubly Linked List

8 of 25

Doubly Linked List (with data)

9 of 25

Doubly Linked List

​

  • Advantages
    • Allows for efficient traversal in both directions
    • Easier implementation for certain algorithms
  • Disadvantages
    • Extra memory overhead for additional pointer
    • Slower insertion and deletion compared to singly linked lists

10 of 25

Circular Singly linked List

11 of 25

Circular Singly linked List (with data)

12 of 25

Circular Doubly linked List

13 of 25

Circular Doubly linked List (with data)

14 of 25

Circular Linked List

​

  • Advantages
    • Efficient for rotating elements
    • Useful for implementing circular buffers and queues
  • Disadvantages
    • Difficult to implement
    • Traversal requires extra logic to avoid infinite loop'

15 of 25

Applications of Linked Lists

​

  • FileSystem - storing file data in blocks linked together
  • Browser History - storing visited URLs in a linked list
  • Music Player - storing tracks in a playlist

16 of 25

Advantages of Linked Lists

​

  • Dynamic size - can grow or shrink as needed
  • No need to allocate memory in advance
  • Efficient insertion and deletion operations

17 of 25

Disadvantages of Linked Lists

​

  • Sequential access only - no random access
  • Extra memory overhead for pointers
  • Traversal requires O(n) time

18 of 25

Creating a Linked List

​

  • Initialize an empty linked list
  • Add nodes to the list by setting the previous node's pointer to the new node

19 of 25

Relationship between LinkedList and Node

The relationship between LinkedList and Node is a composition relationship, meaning that a LinkedList is composed of multiple Node objects.

Understanding the Relationship:

  • Node is a building block of LinkedList
  • Each Node contains data and a reference (or pointer) to the next Node in the sequence.
  • LinkedList manages Node objects
  • The LinkedList class acts as a container that organizes and maintains the sequence of Node objects.
  • It provides operations like insertion, deletion, searching, traversal, and reversal.

​

20 of 25

LinkedList Class in Python

​

  • Create a Node class to represent a node in the linked list
  • Create a LinkedList class to manage the list
  • Implement methods for adding, deleting, and traversing the list

21 of 25

Traversing a Linked List

  • Start at the head node
  • Loop through each node by following its pointer to the next node
  • Stop at the last node

22 of 25

Accessing Elements in a Linked List

​

  • Similar to traversing a list, but stop at the desired element

23 of 25

Inserting Elements into a Linked List

​

  • Find the node before the insertion point
  • Set its pointer to the new node
  • Set the new node's pointer to the old next node

24 of 25

Deleting Elements from a Linked List

​

  • Find the node before the node to be deleted
  • Set its pointer to the node after the deleted node

25 of 25

Finding the Length of a Linked List

​

  • Traverse the linked list and count each node visited