JD

Linked Lists

Linked Lists

General Overview

  • Definition and Purpose: A linked list is suitable for use in many kinds of general-purpose databases and can replace an array as the basis for other storage structures such as stacks and queues.

  • Usage: Linked lists can be utilized in many situations where one might typically use an array.

  • Structure: In a linked list, each data item is encapsulated within a link or a node.

  • Link Definition: A link is an object of a class called Link.

Internal Structure of a Linked List

  • Each link object contains:

    • A reference (typically called next) to the subsequent link in the list.

    • A field in the list itself holds a reference to the first link.

  • Reference Explanation: A reference is a numerical representation that indicates the memory address of an object in the computer's memory.

  • Storage Difference: Primitive types (e.g., int, double) are stored differently compared to objects.

Class Definition

  • Class Link or Node:

class Link {
  public int data;
  public Link next; //Reference to the next link
}

  • Self-Referential Class: This class definition is termed self-referential because it contains a field (next in this case) of the same type as itself.

Differences Between Linked Lists and Arrays

  • Access Method:

    • In an array, each item occupies a specific position that can be accessed directly using an index number.

    • In a linked list, access to a particular element requires traversing the chain of elements from the start: you must follow the links from the first item, to the second, to the third, and so on.

  • Direct Access: Unlike arrays, where direct access to data items is possible through index numbers, linked lists depend on relationships between items for locating data items.

Operations on a Simple Linked List

  • Basic Operations:

    • Inserting an item at the beginning of the list.

    • Deleting the item at the beginning of the list.

    • Iterating through the list to display its contents.

  • These operations suffice to use a linked list as the foundation for a stack.

  • Code Example: firstLinkedList.java includes two classes – Link class or Node class and LinkList class.

Class LinkList

  • The LinkList class maintains a single data item:

    • A reference to the first link in the list, referred to as first or front.

    • This reference constitutes the only permanent information the list retains about the location of any of its links.

  • Reference Navigation: Additional links are found by following the chain of references from first using the next field of each link.

Main Methods of LinkList

  • Constructor: The constructor for LinkList sets first to null explicitly. When first is null, this signifies that there are no items on the list. Conversely, if items exist, first will contain a reference to the initial link.

  • isEmpty() Method: Utilizes the null state of first to determine whether the list is empty.

insertFirst() Method

  • Functionality: This method inserts a new link at the beginning of the list, which is the simplest insertion point since first already points to the initial link.

  • Insertion Logic:

    1. The next field in the newly created link is set to point to the old first link.

    2. Change first to point to the newly created link.

  • Code Implementation:

public void insertFirst(int id) {
  Link newLink = new Link(id);
  newLink.next = first;
  first = newLink;
}
deleteFirst() Method

  • Functionality: This method acts in opposition to insertFirst(). It disconnects the first link by redirecting first to point to the second link found via the next field in the first link.

  • Code Implementation:

public Link deleteFirst() {
  Link temp = first;
  first = first.next; //delete it
  return temp; //return deleted link
}
displayList() Method

  • Purpose: Displays the linked list by starting at the first link and traversing through each link until the end is reached.

  • Code Implementation:

public void displayList() {
  System.out.print("List (first -> last): ");
  Link current = first; //start at the beginning
  while(current != null) {
    current.displayLink();
    current = current.next;
  }
  System.out.println();
}
Finding and Deleting Specific Links

  • Find Method: Searches for a link with a specific key value.

    • Code Implementation:

  public Link find(int key) {
    Link current = first;
    while(current.data != key) {
      if(current.next == null) return null; //key not found
      else current = current.next;
    }
    return current; //key found
  }

  • Delete Method: Deletes a link with the specified key value.

    • Requires maintenance of both current and previous links to establish connections post-deletion.

    • Code Implementation:

  public Link delete(int key) {
    Link current = first;
    Link previous = first;
    while(current.data != key) {
      if(current.next == null) return null; //didn't find it
      else {
        previous = current;
        current = current.next;
      }
    }
    if (current == first) first = first.next;
    else previous.next = current.next;
    return current;
  }

Double-Ended Lists

  • Overview: A double-ended list features an additional reference to the last link alongside the first. This allows new links to be inserted directly at the end as well as the beginning.

  • Efficiency Considerations: While inserting at the end of a single-ended list necessitates traversing the entire list which can be inefficient, a double-ended list mitigates this by offering direct access to the last link.

  • Class Representation: The DoubleEndedList class contains two data items – first and last, pointing to the respective ends of the list. If the list contains a single item, both references will point to that item. If empty, they will be null.

insertLast() Method

  • Functionality: This method facilitates insertion at the end of the list using a similar process as insertFirst(). It modifies last.next to point to the new link and then updates last to reference the new link.

Deletion in Double-Ended Lists

  • Challenge: Deleting the last link remains problematic since there is no reference to the next-to-last item, which requires alteration of its next field upon deletion.

  • Solution: For seamless deletion of the last element, a doubly linked list is more appropriate.

Linked-List Efficiency

  • Time Complexity:

    • Insertion and deletion at the beginning of a linked list takes O(1) time.

    • Searching through the list or finding, deleting, or inserting next to a specific item on average requires O(N) comparisons.

  • Comparison with Arrays: Despite arrays also being O(N) for these operations, linked lists tend to be faster since their elements don't need movement during insertion or deletion. This leads to significant efficiency improvements, especially when comparing the time taken for copying items versus mere comparisons.

  • Memory Usage: Linked lists utilize only the exact amount of memory required, dynamically expanding to use available memory, while arrays have fixed sizes that can lead to inefficiencies when too large or too small.

Sorted Lists

  • Definition: In a sorted list, items are arranged in ascending order based on key value, akin to a sorted array.

  • Advantages:

    • Speed of insertion is notably improved since elements do not require shifting.

    • Lists can dynamically expand unlike arrays which are fixed in size.

  • Implementation Challenge: Implementing a sorted list can be more complex than managing a sorted array.

Inserting into Sorted Lists

  • Insertion Process:

    1. Search for the appropriate position to insert the item by traversing the list.

    2. Once the correct position is identified, insertion is completed by updating the next references of neighboring links.

  • Special Cases: Special scenarios may arise where the new link needs to be inserted at the beginning or the end of the list.

Doubly Linked Lists

  • Overview: A standard linked list presents challenges when attempting backward traversal. A doubly linked list permits traversal in both directions due to each link containing two references: one for the previous link and one for the next link. This allows for easier navigation typical in applications like text editors.

Class Definition for Doubly Linked List

  • Class Link Structure:

class Link {
  public int data;
  public Link next;
  public Link previous;
}
Display Methods for Doubly Linked Lists

  • Traversal Methods: Two methods demonstrate traversal:

    • displayForward(): move from the start to the end.

    • displayBackward(): initiated at last, traverses to the start by following previous links.

Insertion Methods in Doubly Linked Lists

  • insertFirst() Method: Acknowledges the previous link in the old first to point to the new link, updates the next fields accordingly, and resets the first pointer.

  • insertLast() Method: Replica of insertFirst(), but focused on the end of the list.

  • insertAfter() Method: This method allows for the insertion of a new link after a link with a specified key value; it requires finding the current link similarly to the find() routine in the linkList2.java program. Upon finding the current link, connections must be established between the new link and the subsequent link.