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

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

5.1.7 - stack at a diagramatic level

5.1.9 - queue at a diagramatic level

And here - List at an algoritmic/coding level

 

add (head)

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

 
17    public void insertAtHead(Object data){ 
18        Node newNode= new Node(data); 
19        newNode.setNext(head); 
20        head = newNode; 
21    }

 

add (tail)

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){ 
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 ne 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()) < 1){ 
66            head = newNode; 
67        }else{ 
68            while(newNode.getData().toString().compareTo(current.getData().toString()) > 1 
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        Node current = head; 
96        while(current.getNext() != null){ 
97            System.out.println(current.getData().toString()); 
98            current.getNext(); 
99        } 
100    }


isEmpty

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


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

 

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