Linked Lists Overview

Linked Lists

• A linked list is a linear data structure that stores data dynamically.
• It's a series of connected nodes.
• Each node stores data and the address (pointer) of the next node.
• Each node has two fields: data and a pointer to the next node.
• The last node's pointer is null.
• Linked lists can grow and shrink in size as needed.

Accessing a Linked List

• Access is through the head node, which points to the first node.
• The last node is called the tail node and points to null.

Node Structure

• Each node contains data (the actual value or element).
• A pointer to the next node in the sequence (memory address/reference).

Memory Allocation

• Elements are scattered randomly in memory.
• This differs from arrays, which store elements contiguously.

Adding Elements

• Easy to add elements (new links) at any location.
• Requires adjusting pointers.

Deleting Elements

• Easy to delete elements.
• Requires adjusting pointers to bridge gaps.

Types of Linked Lists

• Singly linked list: Each node points only to the next node. Traversal is one-way.
• Doubly linked list: Each node points to both the next and previous nodes. Traversal is two-way.
• Circular linked list: The last node points back to the first node, creating a cycle.

Advantages

• Dynamic Size: Can grow or shrink at runtime.
• Insertion/Deletion: Efficient, especially with large lists, because you don't need to shift elements around.
• Flexibility: Easily reorganized and modified without needing contiguous memory.

Disadvantages

• Linear Access: Requires traversal to access elements by index, unlike arrays.
• Extra Memory: Needs extra memory to store pointers.

Operations

• Insertion: Adding a new node at the beginning, end, or anywhere in between.
• Deletion: Removing a node from the beginning, end, or interior of the list.
• Searching: Traversing the list to find a specific value.

The Node Class

• Attributes:
  • element: the actual data in the node.
  • next: points to the next node in the list.

The Linked List Class

• Contains:
  • head: A pointer to the first node in the list (or null if empty).
• Additional methods may be needed for specific operations like searching, inserting, deleting etc.

Empty and Full Lists/Nodes

• isEmpty(): Checks if the Linked List is empty (head is null).
• isFull(): Checks if creating a new node is possible (i.e. memory allocation failed).

Inserting a Node

• At the beginning: Make new node point to the old head, then make head point to the new node.
• In sorted order: Locate where it belongs in the list and adjust pointers to place new node.
• At the end: Find the current last node, then make the next of the last node point to the new node added.

Deleting a Node

• At the beginning: Make the head pointer point to the node after the deleted one.
• Interior Node: Traverse to find the node before the deleted one, change its 'next' pointer to point to the node one past the deleted node.
• At the end: Traverse to find the node before the last node, then make its next pointer null.

Finding the List Size

• count(): Traverses the list and counts the number of nodes.

Getting the First Element

• get(): Returns the data from the first node (or an appropriate message if empty).

Updating a Value

• update(): Finds a node with a matching value, then changes its data.