Question

 Describe the Ranked Sequence ADT (give a definition, set of 
operations). Compare the array-based and the doubly linked list
implementation of the Ranked Sequence ADT.

Please write alot do note give me code. Just give me a indepth explination. PLease

Answer 1

Answer:------------

Ranked Sequence ADT :----------- A ranked sequence is a collection of items arranged in a linear order, where each item has a rank defining the relative ordering of that item in the sequence. Note: Stacks, queues and dequeues are restricted type of sequences which provide an access to specific items only. 
Operations (methods) on ranked sequences: 
returnItem (rank) Returns the item at the specified rank 
replaceItem (rank, newItem) Replaces the item at the specified rank with newItem 
insertItem (rank, newItem) Inserts newItem at the specified rank 
deleteItem (rank) Deletes the item at the specified rank 
size () Returns the size of the sequence 
empty () Returns true is the sequence is empty 
traverse () Processes each node in the sequence in a specified way 

Comparison the array-based and the doubly linked list implementation of the Ranked Sequence ADT.

An array-based implementation of a ranked sequence:----------- Consider array S[i] with n objects, where i is the reference to the object with rank i. Algorithm returnItem (rank): return S[rank] O(1) efficiency Algorithm replaceItem (rank, newItem): O(1) efficiency S[rank] := newItem Algorithm insertItem (rank, newItem): O(n) efficiency for i = n-1 to rank do S[i+1] := S[i] S[rank] := newItem n++ Algorithm deleteItem (rank): O(n) efficiency item := S[rank] for i = rank to n-1 do S[i] := S[i+1] n-- return item size() and empty() methods are O(1), and traverse() is O(n) method.

A doubly linked list implementation of a ranked sequence:--------------- 1. the insertItem method (cont.) public void insertItem (int rank, Object item) throws BoundaryViolationException { if (rank != size()) checkRank (rank); DLNode next = nodeAtRank (rank); DLNode prev = next.getPrev(); DLNode node = new DLNode (item, next, prev); next.setPrev(node); prev.setNext(node); size++; } The efficiency of this method is O(n/2), because of the nodeAtRank method, which in the worst case traverses the half of the sequence.

2.the deleteItem method public Object deleteItem (int rank) throws Boundary ViolationException { checkRank (rank); DLNode node = nodeAtRank(rank); DLNode next = node.getNext(); DLNode prev = node.getPrev(); prev.setNext(next); next.setPrev(prev); size - -; return node.getData(); } The efficiency of this method is O(n/2), because of the nodeAtRank method, which in the worst case traverses the half of the sequence.