Rohit Singh Rohit Singh - 7 months ago 8
Java Question

How position based sequence ADT inserts an element in O(1) time?

I was reading about position based sequences.(Michael T.Goodrich) chapter-4 (Sequences).
What i understood is that positional sequence keeps on adding nodes in linear order.(Based on Doubly linked list ) and each node may point to some other node/s
for eg. take a simple tree having four nodes a,b,c,d implemented by positional sequence.P(having nodes p1,p2,p3,p4) enter image description here

Now if i want to add new tree node "e" as right child of "b".For this i will simply add this node in p5, then i will make references of e.
Book says it adds a node in O(1) time.
My point is, To add e as right child of b, don't we need position of b which we will get from position of "a"(link hopping).How come it is not O(n).

one of the solution i found in stackoverflow itself is the following code...

public interface Position
{
Object element();
}


Make a class Node implementing Position:

public class Node implements Position
{
private Object data;
private Node next;
private Node prev;

public Node(Node prev, Object data, Node next)
{
this.prev = prev;
this.data = data;
this.next = next;
}

public Object element() // Method of interface Position
{
return data;
}

public void setData(Object data)
{
this.data = data;
}

public void setNext(Node next)
{
this.next = next;
}

public void setPrev(Node prev)
{
this.prev = prev;
}

public Node getNext()
{
return next;
}

public Node getPrev()
{
return prev;
}

}


Make a class List implementing the List ADT:

// this is a List ADT implemented using a Doubly Linked List

public class List
{
private Node first;
private Node last;
private int size;

List()
{
first = null;
last = null;
size = 0;
}

public int getSize()
{
return size;
}

public boolean isEmpty()
{
return (size==0);
}


// Accessor methods

public Position first()
{
return first;
}

public Position last()
{
return last;
}

public Position before(Position p) throws Exception
{
Node n = (Node) p;
try{
return n.getPrev();
}catch(NullPointerException ex)
{
throw new Exception("Position Doesn't Exists");
}
}

public Position after(Position p) throws Exception
{
Node n = (Node) p;
try{
return n.getNext();
}catch(NullPointerException ex)
{
throw new Exception("Position Doesn't Exists");
}
}

// Update methods

public void insertFirst(Object data)
{
Node node;
if(isEmpty())
{
Node prev = null;
Node next = null;
node = new Node(prev,data,next);
first = node;
last = node;
}
else
{
Node prev = null;
Node next = first;
node = new Node(prev,data,next);
first.setPrev(node);
first = node;
}
size++;
}

public void insertLast(Object data)
{
Node node;
if(isEmpty())
{
Node prev = null;
Node next = null;
node = new Node(prev,data,next);
first = node;
last = node;
}
else
{
Node prev = last;
Node next = null;
node = new Node(prev,data,next);
last.setNext(node);
last = node;
}
size++;
}

public void insertBefore(Position p, Object data) throws Exception
{
Node cur = (Node) p;
Node prev;
try{
prev = cur.getPrev();
}catch(NullPointerException ex)
{
throw new Exception("Position Doesn't Exists");
}
Node next = cur;
Node node;
node = new Node(prev,data,next);
next.setPrev(node);
if(cur!=first)
prev.setNext(node);
else
first=node;
size++;
}

public void insertAfter(Position p, Object data) throws Exception
{
Node cur = (Node) p;
Node prev = cur;
Node next;
try{
next = cur.getNext();
}catch(NullPointerException ex)
{
throw new Exception("Position Doesn't Exists");
}
Node node;
node = new Node(prev,data,next);
prev.setNext(node);
if(cur!=last)
next.setPrev(node);
else
last=node;
size++;
}

public Object remove(Position p) throws Exception
{
Node n = (Node) p;

Object data = n.element();
if(isEmpty())
{
throw new Exception("List is Empty");
}
else
{
Node prev,next;
if(n==first && n==last)
{
first = null;
last = null;
}
else if(n==first)
{
prev = null;
next = n.getNext();
next.setPrev(prev);
first = next;
}
else if(n==last)
{
prev = n.getPrev();
next = null;
prev.setNext(next);
last = prev;
}
else
{
prev = n.getPrev();
next = n.getNext();
prev.setNext(next);
next.setPrev(prev);
}
size--;
}
return data;
}

}


PEACE

Answer

I understand this situation as following. For add new item into the list we have to perform to tasks:

First one: find target item, after which we want to add new item.

Second one: add item and change links.

As you correctly noted, in case of linked list, first operation depends on the amount of item in the list, and will take (maximally) O(n). But, for example in case of array list it can take O(1).

I guess, book says about second task, when target item is already found. And this operation really will take constant amount of operations - O(1), if you are working with linked list. The same operation on array list can take O(n).

Regarding to your comment. Just compare:

Position based

  • get(i) is O(n)
  • add(item) is O(1) advantage
  • addToPosition(i, item) is O(n)
  • delete(item) is O(1) advantage
  • delete(i) is from O(1) to O(n)

Ranked based

  • get(i) is O(1) advantage
  • add(item) is from O(1) to O(n)
  • addToPosition(i, item) from O(1) to O(n)
  • delete(item) is from O(1) to O(2n)
  • delete(i) is from O(1) to O(n)

So, you should to know advantages of both of types, for use it depending on situation. For example, if you need large amount of add and delete operations - you should use LinkedList, but when you need just access items by index and there is few of add and delete operations - choose ArrayList.

Comments