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

push( ) *
pop( )
isEmpty( ) *

Link: 5.1.9 - queue at a diagramatic level

enqueue( ) *
dequeue( )
isEmpty( ) *

And here - List at an algorithmic/coding level

add at tail - which would be push *
add at head - which would be enqueue *
insert (in order)
delete
list
isEmpty *

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:

And before even doing this, we need to check to make sure the list is not empty.
And if it is, just make head to be the new Node.
Make your new Node, and link it to head.
Then make the head variable to be changed to be your new Node.
(You actually don't need the first check of isEmpty( ); it will work without it since setNext(head) will properly set the next to be null.)

 
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

And before even doing this, we need to check to make sure the list is not empty.
And if it is, just make the head to be the new Node.
Else, we traverse:
Make a Node called "current", and set it initially to head.
Then, while we are not to the end of the list (which we know because getNext( )will not be null)
shift the current one link up each time.
Then, after we have reached the end (which we'll know because getNext( ) will be null),
Set the next of the current (which is was the tail) to be the new Node.


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.

So start with a new Node, and "current" starting at the head.
But you will also need to keep track of the "previous" node for linking purposes later on.
Check first of all for the possibility that your new Node is the least in the order and so needs to be the head:
Using a compare operation, if this is the case, your newNode needs to point to the head, and then it becomes the head.
Otherwise, you will loop through the list, each time, checking if the node where you are at is greater than the node you are adding, and each time moving the previous up to the last current.
When it is no longer the case that your node is greater, you have found the position for the new node.
So you will link it there by setting the "previous"'s next to be your newNode, and your newNode's next to be the current.


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.

Start with a current and a previous node, as with all list traversals.
Before you get going check to see if the head is equal to what you want to delete, and if so, set head to be its next.
If that wasn't the case you need to keep looking, one step at at time.
As with other traversals, as long as the getNext( ) does not return null, keep on looking.
And if at any point you find what you are looking for with a .equals, you need to link around it with:
Make the previous point to what the current currently is pointing to. That breaks the link to current.

       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.................................

Only not if isEmpty( ),
Starting with a "current" node being the head.
Until you get to a current whose getNext( ) is null.
One step at a time, print out the data at each node.
And you'll have to print out one last time outside of the loop when you get to the end.


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.

So we return the boolean true or false of head == 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:

Make a temporary Node the head, so as not to lose acces to its data.
Make the head to be the head.getNext( ).
Return the data of the temporary Node.

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