Simple Data Structures| Linear Data Structures | Lists

Simple Data structures

The basic structure to represent unit value types are bits, integers, floating numbers, etc. The collection of values of basic types can be represented by arrays, structure, etc. The access of the values are done in constant time for these kind of data structured

Linear Data Structures

Linear data structures are widely used data structures we quickly go through the following linear data structures.

Lists

List is the simplest general-purpose data structure. They are of different variety. Most fundamental representation of a list is through an array representation. The other representation includes linked list. There are also varieties of representations for lists as linked list like singly linked, doubly linked, circular, etc. There is a mechanism to point to the first element. For this some pointer is used. To traverse there is a mechanism of pointing the next (also previous in doubly linked). Lists require linear space to collect and store the elements where linearity is proportional to the number of items. For e.g. to store n items in an array nd space is required were d is size of data. Singly linked list takes n(d + p), where p is size of pointer. Similarly for doubly linked list space requirement is n(d + 2p).

Array representation 

1. Operations require simple implementations.
2. Insert, delete, and search, require linear time, search can take O(logn) if binary search is used. To use the binary search array must be sorted. 
3. Inefficient use of space

Singly linked representation (unordered)

1. Insert and delete can be done in O(1) time if the pointer to the node is given, otherwise O(n) time.
2. Search and traversing can be done in O(n) time
3. Memory overhead, but allocated only to entries that are present.

Doubly linked representation

1. Insert and delete can be done in O(1) time if the pointer to the node is given, otherwise O(n) time.
2. Search and traversing can be done in O(n) time
3. Memory overhead, but allocated only to entries that are present, search becomes easy.   

boolean isEmpty ();   

Return true if and only if this list is empty.

int size ();

Return this list’s length.

boolean get (int i);

Return the element with index i in this list.

boolean equals (List a, List b);

Return true if and only if two list have the same length, and each element of the lists are equal

void clear ();  

Make this list empty.

void set (int i, int elem);  

Replace by elem the element at index i in this list.

void add (int i, int elem);  

Add elem as the element with index i in this list.  

void add (int elem);

                              Add elem after the last element of this list.

void addAll (List a List b);  

Add all the elements of list b after the last element of list a.

int   remove (int i);

Remove and return the element with index i in this list.

void visit (List a);

Prints all elements of the list