Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎


posted Mar 27, 2018, 9:58 AM by Konstantinovich Samuel
java linked lists:

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


   Node next,prev
   int data

Node Methods:
Node getNext()
Node getPrev()
int getValue()
String toString
(also all the set methods to go with them)

MyLinked List
   Node first
   Node last
   int length   

Linked list methods 
String toString
int get(n)
void set(int index,int value)
int size()

 Be careful with: 
   -empty lists
   -start/end nodes

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

Suggested Phases:
Phase I:

MyLinkedList() - make an empty list.

boolean add(int value) 
    - adds the value to end (try adding to the front first, for testing purposes)
int size() 
    - return the number of elements in the list
    - returns a string representation of the list of n elements formatted like: 
        [ v0, v1, v2, v3, ... vn-1
          An empty list is just []
int get(int index) 
    - return the value of the element at the specified index (0 based)
int set(int index,int newValue)
    - change the value of the element at the specified index to the newValue, return the old value  

Phase II:
int indexOf(int value) 
    - returns the index of the 1st occurrence of the value in the linked list, -1 if not found.
void add(int index, int value)    
    - insert a new element at the specified index, 0 at the front, size() at the end. 
int remove(int index) 
    - remove the element at the specified index, returns the value removed

-Any exceptions that the actual LinkedList contains:  get,set,add,remove