2018-12-13 LinkedList

posted Dec 13, 2018, 6:11 AM by Konstantinovich Samuel   [ updated Dec 14, 2018, 6:49 AM ]
DO NOW:
Read the entire lab. Discuss the discussion points with your neighbors.
Notice there are some warnings.

Please do not get me candy/chocolate (nor flowers) for the holidays.

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


DO NOT:
Loop through the list by index, especially in your toString() !!!


(Discussion point1. Why don't you want to use get(index) in your toString() ?  )

INSTEAD:
Traverse the list by keeping track of which node you are currently looking at using a Node variable.
Traversing the list in this manner is useful, but can only be done inside of the LinkedList class as it has direct access to the nodes.

Node current = first_node
while current != null:
  print current.value()
  current = current.next()

By making your while loop stop early:
-You can use this to find a node with a particular value
-You can use this to find the n'th node


Having a method to get the nth node is very useful. You would use such a method in many of your other methods.
Keep in mind: Any MyLinkedList method that returns a Node or takes a Node parameter should be private!


Git Repo:

MKS21X-LinkedList


Node
Fields:
    Node next,prev
    Integer data
Methods:
    Node next()
    Node prev()
    void setNext(Node other)
    void setPrev(Node other)
    Integer getData()
    Integer setData(Integer i)
    String toString()


MyLinkedList
Fields:
   Node start
   Node end
   int length   

Constructor:
      MyLinkedList() - make an empty list.

Public Methods:   (This is a good order to try to implement them)
     boolean add(Integer value)
     int size()   
     String toString()   //note you don't have get(index) yet, nor would you want to use it here

    Having a private method to get the nth node is very useful.
    You would use such a method in many of your other methods (hinted with a *)
    (Discussion point2. Why should getNthNode be private?)

*    Integer get(int index) 
*    Integer set(int index,Integer value)

     boolean contains(Integer value)
     int indexOf(Integer value)

*    void add(int index,Integer value) 
*    Integer remove(int index) 
*    boolean remove(Integer value) //a private method to find a node you want could be useful here
edit: fixed typo, remove(value) returns boolean

Remember to throw any exceptions that the actual LinkedList would throw. (Look at the documentation)

(Discussion point3. Regarding your methods, what are several situations that may cause special cases ? )





Comments