Return to the Lecture Notes Index

15-200 LinkedList Manipulation Problems

Introduction

Some people have been asking me for a quick sample of linked list problems to try for practice. Below is a list of ideas. You might try them using the linked list and node classes from the exam.

Some Ideas

void insertInOrder (Comparable thing)
  -- assume a sorted list, add new item in right order
  -- can be specified for least to greatest or greatest to least

void mergeList (LinkedList sortedList)
  -- assume both lists are sorted -- keep new list that way

void sortList()
  -- given a list sorts from highest to lowest or lowest to highest
  -- almost certainly makes sense to implement insertInOrder() as
     a helper method

void moveHigher (LinkedList someList, comparable threshhold)
  -- can be specified for sorted and unsorted lists
  -- move all items above some value to supplied list
  -- variant: not a supplied list, create a new list and return

void moveLower (LinkedList someList, comparable threshhold)
  -- can be specified for sorted and unsorted lists
  -- move all items below some value to the supplied list
  -- variant: not a supplied list, create a new list and return

void movetoFront (Comparable item)
  -- move each instance of the supplied item to the front of the list
  -- variants to move items greater than or less than supplied
     item to front of list

void moveToTail (Comparable item)
  -- move each instance of the supplied item to the tail of the list
  -- variants to move items greater than or less than the
     supplied item to tail of list

Comparable removeItem (Comparable item)
  -- remove and return the first instance of the item from the list

void removeAllItems (Comparable item)
  -- remove all intances of an item from a list

Comparable removeNth ()
  -- remove and return the Nth item of the list
  -- be carefult  check directions: starting w/0 or 1?

void reverseList()
  -- reorganize the list so the items are in reverse order
  -- iterative and recursive variations; either could be required

void everyOtheritem(LinkedList l)
  -- remove every other item from the linked list and add it to the
     supplied linked list l
  -- can also be written w/out paramters to return a newly created linked
     list
  -- be careful: which item to start with?

LinkedList cloneList()
  -- makes a copy of the list, including nodes (shallow; doesn't copy
     items organized by list)