Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-04-03 Linked Lists

posted Apr 3, 2017, 6:48 AM by Samuel Konstantinovich
Traversing the list is useful: (works both directions for a doubly linked list)
node = first_node
while node!=null:
  //do stuff with value_of_node
  node = next_node

-You can use this to find a node with a particular value
-You can use this to find the n'th node


Let us talk about our algorithms with respect to doubly linked lists

Constructor:
MyLinkedList() - make an empty list.

Methods:

I won't talk about:
 -toString
 -get(n)
 -set(n,value)

add(index,value)
 Be careful with: 
   -empty lists
   -start/end nodes

remove(index)
  -check size first
  -get to the node
  -remove the node with another method


OPTIONAL methods not part of the list, but useful internal to the list:
private node getNode(index)
private remove(node)
private insertAfter(node toBeAdded, node location)
private insertBefore(node toBeAdded, node location)
Comments