TMF1434: Data Structure and Algorithms - Linked Lists (Part 2)

Unordered Linked Lists

• Unordered linked lists are derived from the abstract class linkedListType.
• To search for a given item in an unordered linked list:
  • Compare the search item with the current node in the list.
  • If the item is found, return true; otherwise, return false.
  • Repeat the comparison until the item is found or no more data is left in the list.
• To insert a node at the head of an unordered linked list:
  • Create a new node and set it as the first node.
• To insert a node in the middle of an unordered linked list:
  • Use two pointers, p and q.
  • Compare the info of the new node with the info of the current node.
  • If the new node's info is less than the current node's info, insert the new node before the current node.
• To insert a node at the tail of an unordered linked list:
  • Create a new node and set it as the last node.
• To delete a node in an unordered linked list:
  • Consider the following cases:
    • Case 1: The list is empty.
    • Case 2: The node to be deleted is the first node.
    • Case 3: The node to be deleted is not the first node, but is somewhere in the list.
    • Case 4: The node to be deleted is not in the list.

Ordered Linked Lists

• Ordered linked lists are derived from the abstract class linkedListType.
• To search for a given item in an ordered linked list:
  • Compare the search item with the current node in the list.
  • If the item is found, return true; otherwise, return false.
  • Repeat the comparison until an item in the list that is greater than or equal to the search item is found, or no more data is left in the list.
• To insert a node in an ordered linked list:
  • Use two pointers, current and trailCurrent.
  • Consider the following cases:
    • Case 1: The list is initially empty.
    • Case 2: The new item is smaller than the smallest item in the list.
    • Case 3: The item is to be inserted somewhere in the list.
• To delete a node in an ordered linked list:
  • Use two pointers, current and trailCurrent.
  • Consider the following cases:
    • Case 1: The list is initially empty.
    • Case 2: The item to be deleted is contained in the first node of the list.
    • Case 3: The item to be deleted is somewhere in the list.
    • Case 4: The list is not empty, but the item to be deleted is not in the list.