Linear Data structure Variation | 2008-10-15

Portfolio » Application Programming

The general design of the Reversed Array List is not very special, technical speaking, it reverts the indexes of the array list elements. In the term of its data storage, it acts very similar to the Stack, but it reserved all the methods of the Array list......

 

 

Real world model of the Reversed Array List

 

            The general design of the Reversed Array List is not very special, technical speaking, it reverts the indexes of the array list elements. In the term of its data storage, it acts very similar to the Stack, but it reserved all the methods of the Array list.

 

            As we learned the foundation of data structure, the data structure is the simulation of the real world problem and solution. So why do we need this in the real world model after all?

 

            In the case of financial market price data, each incoming data needs to be stored in a cell.  Each of the stored data have properties such as, time, open price, high, low, close, volume, etc.  There are many data types, tick, volume, time, range, etc  For the purpose of our example, we will use minute data.  For every minute in time, we need to store the data in a list.  There will be a lot of data in the list eventually, but we only need manipulate the recent prices but not the prices that are older than the current minute. The best method is to use a reversed array list.   The current minute data is stored in List[0] and each minute in the past is store in the relative position to the current time.  To recall the minute price data of 15 minutes ago, we will simply call List[15].  For data of an hour ago, we will call List[60]

 

 

            As we can see in the chart shows above, its index is in reversed order compare to the Array/ Array List. In Array List, List[0] is the first element inserted to the list and List[k] is the last element insert to the List. (Where 0 and k are the list index where point to the elements). Hence, implementing a variation of the array list that reversed the index is the best solution to this real world problem.

 

 

Implementations

 

            Similar to original normal array list, the implementations of this new variation of Abstract list can be observed and learned on how the array list was implemented. This list is extending to the Abstract List that is under the JAVA AbstractCollection.
( http://java.sun.com/j2se/1.4.2/docs/api/java/util/AbstractList.html )

 

 

AbstractList

            There are interface in the AbstactList  for our new modified of reversed list we will use:

  • void add(int index, Object element)
    Inserts the specified element at the specified position in this list.
  • boolean add(Object o)
    Appends the specified element to the end of this List.
  • abstract Object get(int index)
    Returns the element at the specified position in this list.
  • int indexOf(Object o)
    Returns the index in this list of the first occurrence of the specified element, or -1 if the list does not contain this element.
  • int lastIndexOf(Object o)
    Returns the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.
  • Object remove(int index)
    Removes the element at the specified position in this list.
  • Object set(int index, Object element)
    Replaces the element at the specified position in this list with the specified element.

 

 

ReversedList.java

 

 

           We learned that in the beginning of the programming work, we usually do not look at anything too detail to code but start from the big picture on the scratch. Since this Reversed List is actually variation of the List and is very similar to the ArrayList where it extend to the same AbstactList, we start writing the methods that are essential for the ArrayList and do not consider the difference between them first.

           

            For most of the list, the ability to add, remove, get, set are obviously the priority method that need to be established. So here are the methods that I generated in the code in the very beginning:

 

Essential methods:

 

public void add(int index, E element)

public E remove(int index)

public E get(int index)

public E set(int index, E element)

 

Constructor:

 

The next step, we start thinking of the constructor of ReversedList() to the ReversedList class. The parameter of the input we need is the any type of List

           

   

private List<E> list;   

 

/* Constructor of the list

     * @list:   List

     */

    public ReversedList(List<E> list)

    {

        this.list = list;

}

 

 

 

Array List

 

            Here now we consider a little bit detail on the essential method I mentioned above. But we are now still make the implementation same as the ArrayList without the index reversed:

 

public void add(int index, E element)

{

        list.add( index, element );

}

 

public E remove(int index)

{

        return list.remove(index);

}

 

public E get(int index)

{

        return list.get(index);

}

 

public E set(int index, E element)

{

        return list.set( index, element );

}

 

 

 

Detail Algorithm

 

            In this step, we think of the detail of algorithm to implement the reversed index list.  We notice that there is the implementation needed to do the reversal behavior should be done in add(), remove() and set(). We now create a method that does the changing whenever we call these methods.

    /* Method reverseIndex: Reverse the list index

     * @index:  List Index

     * @return: Integer of index number

     */

    private int reverseIndex(int index)

    {

        return ( (size()-1) - index );

}

 

 

 

After that, we change the parameter of the add(), remove() and set() as well:

 

 

    /* Method add: Add specific element to the last element

     * @index:      List Index

     * @element:    List element

     * @return:     void

     */

    @Override

    public void add(int index, E element)

    {

        list.add( (reverseIndex(index) + 1), element );

    }

 

    /* Method remove: remove specific list element

     * @index:  List Index

     * @return: list with the specific index element removed

     */

    @Override

    public E remove(int index)

    {

        return list.remove( reverseIndex(index) );

    }

 

    /* Method set: set the element to the index

     * @index:      List Index

     * @element:    List Element

     * @return:     List with the element been set by index

     */

    @Override

    public E set(int index, E element)

    {

        return list.set( reverseIndex(index), element );

    }

 

As we could see, although there are many lines changed in all these method, the “trick” that does all the work is still in the method of reverseIndex () which return integer of ((size ()-1) - index)

 

In the size() method, is acts just same as the list:

 

    /* Method size: Get Size of the list

     * @return: Integer of list size

     */

    public int size()

    {

        return list.size();

    }

 

 

Simulate and Testing fo reverseIndex()

 

            To clearly explain what (size()-1 – index) does and simulate the problem, it should be easier to give few test value to input and evaluate the result below:

 

Input values:

        ReversedList.add(1)

        ReversedList.add(2)

        ReversedList.add(3)

 

How do we make it

        ReversedList[0] to be 3, not 1

        ReversedList[1] to be 2, not 2

        ReversedList[2] to be 1, not 3

 

When we say ReversedList[0], we are actually referring to the last element of the list. ReversedList[1] will be the second last element. In this case,

 

if the input is 0, we do size() which will be 3 ( Because it count from 1, not 0 ), 3 minus 1 will be 2, 2 minus 0 will still be 2.

 

if the input is 1, we do size() which will be 3, 3 minus 1 will be 2, 2 minus 1 will be 1.

 

 

 

What else are missing?

           

            In last step, we are looking on what methods that might need besides all the essential methods mentioned before. To know the Current Index might be useful in our case here.

 

    /* Method currentIndex: Get the most rencent index

     * @return: Integer of last index of the list

     */

    public int currentIndex()

    {

        return list.lastIndexOf(list);

    }

 

    /* Method get: Get the element by the index

     * @index:  List Index

     * @return: List element of the index

     */

 

 

 

main.java

 

The main.java is used to create stance of the object we’ve been worked on.

  1. We create a normal array list
  2. We create the reversed array list
  3. Both lists  do the same operation for us to compare the results.
  4. We create some print out for all the methods operation as a test case to see if it is reliabilities.

 

Testing Results:

 

run:

--- List1 ( Result of Normal List ) ---

0th Element: 1

1th Element: 2

2th Element: 3

3th Element: 4

4th Element: 5

5th Element: 6

6th Element: 7

7th Element: 8

8th Element: 9

--- ReversedList ( Result of Implimented Reversed Index List ) ---

0th Element: 9

1th Element: 8

2th Element: 7

3th Element: 6

4th Element: 5

5th Element: 4

6th Element: 3

7th Element: 2

8th Element: 1

--- Testing of using methods ---

Use add(index) method

Use remove(index) method

Use get(index) method

Use set(index,element) method

Use size() method

Use currentIndex() method

--- ReversedList ( Result after using all methods ) ---

0th Element: 11

1th Element: 10

2th Element: 9

3th Element: 8

4th Element: 7

5th Element: 6

6th Element: 5

7th Element: 4

8th Element: 98

9th Element: 99

BUILD SUCCESSFUL (total time: 0 seconds)