Logout

Home OOP HL Last Next

D.4.10

Construct list algorithms using object references.

 

Teaching Note:

Lists will be restricted to singly linked types. Methods that should be known are add (head and tail), insert (in order), delete, list, isEmpty, isFull.

 

Sample Question:

sdfsdfsf

JSR Notes:

List ADT D.: Coding List as Dynamic

Context of D.4.10 in terms of algorithms responsibility (A repeat of this)

D.4.6 - There, we weren't necessarily thinking about a list, we just wanted to see generally how linking is achieved through self-referential pointers. (Though what we looked at there ended up being a list, it also could have been a tree.)

D.4.10 - Here it's the employment of self-referential classes for implementations of general lists - and though not necessarily thinking stacks or queues, certainly these are useful ways of using lists.

D.4.11 - The use of self-referential classes in lists via the specific ADTs ArrayList and LinkedList. And though able to treat lists as stacks and queues, also searching, deleting, adding in order through whole lists.

And D.4.12 is for tracing through such algorithms.

 

Intro Miscellaneous

From the Teaching Note, first of all note that isFull( ) should not be included in the methods; that's the whole point to lists, they are dynamic - they are never "full". Yes, and ArrayList can be, and so can any static implementation of a stack or queue via an array, but not an actual list.

Next, when reproducing algorithms, make sure you remember the importance if isEmpty( ) when trying to add to or access lists.

And also note that in terms of OOP and inheritance, this does not require you to extend List class to a Stack class and a Queue class, but that that is actually really easy to do: for a Stack class, push just calls addLast, and pop calls removeLast - and with Queue extending List, enqueue just calls addFirst, and dequeue calls removeFirst.

 

A Fundamental Memory-based Understanding

If you wish, this animation is great to slow things down and look at what's literally happening line by line, and at the memory level. Note though that the insertion happens from the front, so it is an enqueue.

Animation of Adding to A List - With this you can go step by step.

YouTube Video of the Animation with Commentary:

(back up of that video)


A Repeat here in the Option at a Deeper Level

A lot of this you have recently seen in Topic 5. Remember that for Topic 5, it is to a level of diagramatic understanding, but with the OOP Option Extension, it is to an algorithmic, coding level.

Link: 5.1.7 - stack at a diagramatic level

Link: 5.1.9 - queue at a diagramatic level

And here - List at an algorithmic/coding level

 

You can learn these two four different levels, and any of the top three could be the means of testing them:

I Ok, I get what's going on with the algorithm.

II. I can diagram it.

III. I can write pseudocode for it.

IV. I can code it in Java

 

Add (Head)

which could be a stack push( )

In words: since we have access to the head, this is easy:

 
17    public void insertAtHead(Object data){ //This is the same as addToFront in the D.4.6 Basic List class
18          if(isEmpty()){
19              head = new Node(data);
20            }
21          else{
22              Node newNode= new Node(data); 
23              newNode.setNext(head); 
24              head = newNode; 
25           }
26    }

 

Add (Tail)

which could be a queue enqueue( )

In words: for this, since we only have access to the head, we will have to first traverse the list from the head to the tail


23    public void insertAtTail(Object data){ //This is the same as addToEnd in the D.4.6 Basic List class
24        if(isEmpty()){ 
25            head = new Node(data); 
26        } 
27        else{ 
28            Node newNode = new Node(data); 
29            Node current = head; 
30            while(current.getNext() != null){ 
31                current = current.getNext(); 
32            } 
33            current.setNext(newNode); 
34        } 
35    }



Insert (In Order)

In words: We will need to traverse up the chain (assuming it's already in order) and when what we have is greater than where we are at, that's where our new node goes.


60    public void insertInOrder(Object data){ 
61        Node newNode = new Node(data); 
62        Node current = head; 
63        Node previous = null; 
64        if(data.toString().compareTo(head.toString()) < 0){ 
66            newNode.setNext(head)
66            head = newNode; 
67        }else{ 
68            while(newNode.getData().toString().compareTo(current.getData().toString()) > 0 
69                    && current.getNext() != null){ 
70                previous = current; 
71                current = current.getNext(); 
72            } 
73            previous.setNext(newNode); 
74            newNode.setNext(current); 
75        } 
76    }


 

Delete

In words: The idea here is to locate the node you want to delete and link around it.

       public void delete(Object data){ 
77        Node current = head; 
78        Node previous = null; 
79        if(head.getData().toString().equals(data.toString())){ 
80            head = head.getNext(); 
81        } 
82        while(current.getNext() != null){ 
83            previous = current; 
84            current = current.getNext(); 
85            if(current.getData().toString().equals(data.toString())){ 
86                previous.setNext(current.getNext()); 
87                break; 
88            } 
89        } 
90    }


 

List (i.e. list out all items)

In words: This is simply traversing through and doing something at each node.................................


94    public void listAll(){ 
95        if(!isEmpty()){ 
95             //Note, class of 2020, I had an extra printout here, 
95             //for the head, which was not needed
95            Node current = head; 
96            while(current.getNext() != null){ 
97                System.out.println(current.getData().toString()); 
98                current = current.getNext(); 
99            } 
100          System.out.println(current.getData().toString()); 
100        }
101    }


isEmpty

In words: The list is empty if the head is null.


13    public boolean isEmpty(){ 
14        return (head == null); 
15    }

 

And though not included in the Teaching Note, the most important of all, since it is used by both stack and queue would be get first:

getFirst

which could be both a stack pop( ) and a queue dequeue( )

In words:

public Object getFirst(){ 
    Node temp = head; 
    head = head.getNext(){ 
    return temp.getData();
 }

 

The IntelliJ project from which the code above came: Lists-IntelliJ-Implementation.zip

 

 

--------------------------------------

EXTRA OLDER CURRICULUM NOTES - NOT NEEDED BUT YOU MAY WANT TO TAKE A LOOK:

2175     notes  Stacks (implement by a linked list)                                             
2177      code   
2180 animation  (From the List section above.)

 

2182     notes  Queues (implement by a linked list) (same as Stacks notes above)                 
2185 code