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

2018-03-27

posted Mar 27, 2018, 9:58 AM by Konstantinovich Samuel
java linked lists:
https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html



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



Classes:

Node:
   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()

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


Suggested Phases:
Phase I:

Constructor:
MyLinkedList() - make an empty list.

Methods:
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
toString() 
    - 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

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