Data Structures Lecture: Removing Duplicates

Introduction

• Topic: Removing duplicates in data structures
• Key Points:
  • Two main types of problems when removing duplicates
  • Techniques to handle duplicates in lists and complex structures

Removing Duplicates from Sorted Lists

• Scenario: Given a sorted list, remove duplicates to get a list of unique elements.
• Example scenario provided:
  • Input: [1, 1, 2, 2, 3, 3, 4, 4]
  • Output: [1, 2, 3, 4]
• Steps to solve:
  • Iterate over the list and compare the current element with the next.
  • If a duplicate is found, skip it and move to the next unique element.
• Pseudo-code approach:

  current = head
  while current is not None and current.next is not None:
      if current.value == current.next.value:
          current.next = current.next.next
      else:
          current = current.next
  

• Optimization:
  • Use pointers to traverse the list efficiently.
  • Ensure O(n) time complexity.

Removing Duplicates from Complex Structures

• Scenario: Removing duplicates from complex nested structures/lists
• Example: [1, 2, 3, 4, 2, 3, 4, 5]
  • Remove all instances of duplicates.
• Steps:
  • Create a set to track unique elements.
  • Traverse the entire structure and add only unique elements to the result.
• Pseudo-code approach:

  seen = set()
  result = []
  for item in list:
      if item not in seen:
          seen.add(item)
          result.append(item)
  

• Important Notes:
  • Ensure both time and space complexity are considered.

Practical Implementation Tips

• Coding Practices:
  • Validate edge cases in your lists (e.g., empty list, single element list).
  • Confirm results against known outputs to ensure correctness.
• Common Mistakes:
  • Overlooking the need to update pointers correctly.
  • Not resetting necessary variables after iterations.

Example Explanation

• Example used in class similar to:

  if current.value != current.next.value:
      current = current.next
  else:
      current.next = current.next.next
  

• Explanation:
  • Check if the next value is the same as the current.
  • Adjust the pointers to skip over duplicates.

Complexity Analysis

• Time Complexity: O(n)
  • Efficient for large lists.
• Space Complexity: O(1) for in-place operations; O(n) if using additional data structures like sets.

Homework Practice

• Task: Split a circular linked list into two halves.
• Example:
  • Input: [1, 2, 3, 4, 5, 6]
  • Output: [1, 2, 3] and [4, 5, 6]
• Steps to solve:
  • Use two pointers, slow and fast.
  • Traverse the list until fast reaches the end.
  • Split the list into two halves at the midpoint.
• Submit solutions on the provided educational platform for review.

Conclusion

• Review the methods and approaches for removing duplicates.
• Prepare for the next lecture on optimizing algorithms and their complexities.

Next Steps

• Homework Submission: Ensure homework is submitted on time.
• Next Lecture: Optimization techniques will be covered in detail.