CS2040: ADT and List pt2

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”);  }
}  

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

<Prev ADT and List pt 1                           Next Stack ADT>