Important methods in custom linkedlist
This section will assumes the following definition of MyLinkedList class;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class MyLinkedList {
public Node head;
public void addToFront(int item) {
//create a node that has head as the next node
Node node = new Node(item, head);
//update head to new node
head = node;
}
public int size() {
Node current = head;
while(current != null) {
count++;
current = current.next;
}
return count;
}
public boolean itemExistsAt(int idx) {
return idx >= 0 && idx < size();
}
public String toString() {
Node current = head;
String result = "List: ";
while(current != null) {
result = result + current.data + " ";
current = current.next;
}
return result+"\n";
}
}
Getting an item at a specific index (if any)
Method header
1
2
3
4
5
/**
* @param idx: index of the node whose value should be returned
* @return: data value in the node if node exists, null otherwise
*/
public Integer get(int idx)
Steps involved:
- check if an item exists at the given index using
itemExistsAt(int)- if not, return
null - if it does, go to the item and return its value.
- if not, return
Now “going” to the item requires us to start at head and move forward using next, one at a time. How many times should we move forward by one?
Lets say, the list is head -> 10 -> 70 -> 20 -> 90 -> null.
idx = 0 => move 0 times idx = 1 => move 1 time idx = 2 => move 2 times …
In general, we need to move forward idx times.
1
2
3
4
Node current = head;
for(int i=0; i < idx; i++) {
current = current.next;
}
When the loop terminates, current holds a reference to the Node object whose value needs to be returned.
1
return current.data;
Putting it together, get(int) is defined as:
1
2
3
4
5
6
7
8
9
10
11
12
public Integer get(int idx) {
if(itemExistsAt(idx) == false) {
return null;
}
//guaranteed that item DOES exist at index idx
Node current = head;
for(int i=0; i < idx; i++) {
current = current.next;
}
return current.data;
}
Removing (and returning) an item at a specific index (if any)
Method header
1
2
3
4
5
/**
* @param idx: index of the node which should be removed
* @return: data value in the node if node existed and is now removed, null otherwise
*/
public Integer remove(int idx)
In the same manner as get(int), we will first check if an item exists at the given index. If it doesn’t, we return null.
1
2
3
if(itemExistsAt(idx) == false) {
return null;
}
If it exists, there are two sub-cases.
Case 1: removing item at index 0 (head is updated)
1
2
3
4
5
if(idx == 0) {
int itemRemoved = head.data;
head = head.next;
return itemRemoved;
}
Case 2: removing item at index 1 or beyond (head is not updated)
We need a reference to the node BEFORE the node to be removed. That is, the item at index idx - 1.
1
2
3
4
Node current = head;
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.next;
}
Then we make a backup copy of the value of the node to be removed.
1
2
Node nodeToRemove = current.next;
int itemRemoved = nodeToRemove.data;
Finally, we make the node before the node to be removed refer (using next) to the node after the node to be removed, and return the value of the node removed.
1
2
current.next = nodeToRemove.next;
return itemRemoved;
Putting it together, remove(int) is defined as:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Integer remove(int idx) {
if(itemExistsAt(idx) == false) {
return null;
}
if(idx == 0) {
int itemRemoved = head.data;
head = head.next;
return itemRemoved;
}
Node current = head;
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.next;
}
Node nodeToRemove = current.next;
int itemRemoved = nodeToRemove.data;
current.setNext(nodeToRemove.next);
return itemRemoved;
}
Inserting an item at a given index
Method header
1
2
3
4
5
6
/**
* @param idx: index at which node should be inserted
* @param value: data value of the node to be inserted
* @return: true if node can be inserted at given index, false otherwise
*/
public boolean insert(int idx, int value)
In the same manner as get(int) and remove(int), we will first check if the item can be inserted at the given index.
If the list currently contains 4 items (at indices 0 through 3), a new node can be inserted at index 0 (before the first item) through 4 (after the last item).
Thus, the following condition checks if the item cannot be inserted and the method can return false.
1
2
3
if(idx < 0 || idx > size()) {
return false;
}
Now there are two sub-cases.
Case 1: inserting item at index 0 (head is updated)
1
2
3
4
5
Node node = new Node(value, null);
if(idx == 0) {
node.setNext(head);
head = node;
}
Case 2: inserting item at index 1 or beyond (head is not updated)
We get a reference to the item before where the item needs to be inserted.
1
2
3
4
Node current = head;
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.next;
}
In the diagrams, we illustrate the process when inserting value 50 between 10 and 70.
Finally, we insert the new node after it.
1
2
3
4
5
Node itemAfter = current.next; //itemAfter will be null if node added to end of list
current.next = node;
node.next = itemAfter; //node.next will ne null if node added to end of list
return true;
Putting it together, insert(int, int) is defined as:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean insert(int idx, int value) {
if(idx < 0 || idx > size()) {
return false;
}
Node node = new Node(value, null);
if(idx == 0) {
node.next = head;
head = node;
}
Node current = head;
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.next;
}
Node itemAfter = current.next; //itemAfter will be null if node added to end of list
current.next = node;
node.next = itemAfter; //node.next will ne null if node added to end of list
return true;
}
Homework exercises
Task 1
Add an instance method to class MyLinkedList that returns true if each item in the list is unique, false otherwise. Return true if the list is empty. Some input-output mappings:
[10,70,20,90,30,80] --> true[10,70,20,90,30,70,80] --> false[8] --> true[] --> true[8,8,8,] --> true
Task 2
Add an instance method to class MyLinkedList that reverses the list represented by the calling object. If the state of the list before calling the method is head -> 10 -> 70 -> 20 -> 90 -> null, its state, after the method executes, should be head -> 90 -> 20 -> 70 -> 10 -> null.