Extended Linked List
Each linked list is made up of nodes and each node is connected to one another. However, sometimes when we want to insert the nodes in the middle, BLL(Basic) is not good enough.
e.g: List must always be sorted accordingly
Instead of reimplementing the class extendedlinkedlist, we can just implement the interface thats the same as BLL
Add after takes in a current node and an object, it then assigns the next to a new node if the current is null or assigns the head as a new node.
It then increase the node counts.
RemoveAfter takes in a current node,
It then proceeds to create a temp object
if the current is null and the next is null,
the temp will be the current.next.element
and the current.next will be the current.next.next
The temp will then be return
However, if the current is not null and neither is the head,
the temp will be the head.element
and the head its next element.
It will return the temp.
Tailed Linked List
An enhanced version of ELL.
This is due to the fact that adding to the end would be slow thus an extra data member will be added
However, this could be abit troublesome to maintain when it comes to updating.
The tail is a new data member
We can just add the tail directly but we need to update the tail each time
addafter have to be modified as well such that it will check if its a tail
Make use of the parents method
Circular Linked List
This is to allow cycling, a round robin system.
Each tail will be linked backed to the head node.
However, we need to handle all cases of updating
We will check if the current is null and if its not,
assign the head to a new node,
if after assigning, the tail is null,
we must ensure that the tail is linked to the head
Doubly List Node
We want to move backwards instead of moving forward down the list but there was no prev pointer.
Now we introduce a new prev pointer and change the way the node works by creating DListNode
The DList Node contains a prev pointer
List:
public void addBefore (DListNode <E> current, E item) throws NoSuchElementException {
if (current != null) {
DListNode <E> temp = new DListNode <E> (item,current,current.prev); num_nodes++; if (current != head) {
current.prev.next = temp;
current.prev = temp;
} else { // Insert node before head current.prev = temp;
head = temp;
}
} else { // If current is null, insertion fails. throw new NoSuchElementException(“insert fails”); }
}
if (current != null) {
DListNode <E> temp = new DListNode <E> (item,current,current.prev); num_nodes++; if (current != head) {
current.prev.next = temp;
current.prev = temp;
} else { // Insert node before head current.prev = temp;
head = temp;
}
} else { // If current is null, insertion fails. throw new NoSuchElementException(“insert fails”); }
}
When removing a node, change both next and prev pointers
Assume the node removed is suppose to be A
When removing a node A, we have to ensure that the prev node's next is assigned to the next node after A's head.
We also have to ensure that the head of the next node's head is assigned to the tail of the prev node in front of A's tail.
Creating our own data structure
- Manipulating pointers/references
- Be cautious when it comes to boundary cases
Note: Drawings is useful