Lists, Stacks, and Queues

Lists

A list is a finite, ordered sequence of data items known as elements ("ordered" means that each element has a position in the list)
List ADT (Ye | Shaffer)

insert()

Two implementations: Array-based list | Linked list (Node class)

Comparison of array-based lists and linked lists

	Array-based lists	Linked lists
Pro	no wasted space for each individual element	only need space for the objects actually in the list
Con	size must be predetermined; wasted space for lists with empty slots	overhead for links (an extra pointer added to every node)
Space complexity	$\Omega(n)$ (or greater)	$\Theta(n)$

The break-even point, beyond which the array-based implementation of a list is more space efficient than the linked-list, can be calculated thus:
$n > \frac{DE}{P + E}$ ,
where: $n$ is the number of elements currently in the list,
$D$ is the length of the array-based list,
$E$ is the size of a data element,
and $P$ is the size of a pointer.
(i.e., the array-based implementation is going to be more efficient – if the link field and the element field are of the same size – whenever the array is more than half full).
As a rule of thumb, linked lists are more space efficient when implementing lists whose number of elements varies widely or is unknown.
Useful page at the official Java Tutorials: Primitive data types & bits they take.

Comparison of time complexity for some operations

	append	insert at the head	insert at position i (or delete)	goPrev	goNext	moveToPos
Array based	$\Theta(1)$	$\Theta(n)$
Singly linked	$\Theta(1)$	$\Theta(1)$

Stacks (ADT | Array-based implementation | Linked Stack)

Stack is a LIFO (Last-In, First-Out) list, a list-like structure in which elements may be inserted or removed from only one end (last-in, first-out). Stacks are less flexible than lists, but are easier to implement, and more efficient (for those operations they can do).
Given a stack, the accessible element of the stack is called the top element.
Elements are not said to be inserted; they are pushed onto the stack.
When an element (the last one) is removed, an element is said to be popped from the stack.
Both array-based and linked stacks are fairly easy to implement. Check out the two functions push() and pop() in the ADT of stacks & the different implementations (array-based and linked stacks). The cost for each push and pop operation is only $\Theta(1)$.

The implementation of subroutine calls (recursion) in most programming language runtime environments uses stacks: a subroutine call is implemented by placing necessary information about the subroutine (including the return address, parameters, and local variables) onto a stack. (see Figure 4.22 for an example of calculating factorials using recursion; see Example 4.2 for an interactive form of the factorial function using a stack).

Sample applications of stack:

Finding palindromes
A palindrome is a string that reads the same in either direction: left to right or right to left (e.g., kayak is a palindrome).
Palindromic sequences in DNA often have special meaning (they may be asociated with DNA breakage or serve as recognition sites for restriction enzymes!!)

Checking expressions for balanced parentheses

boolean isBalanced(String expression):
	Create an empty stack of characters.
	balanced = true
	idx = 0
	while balanced is true and idx < the expression's length
		nextChar = expression[idx] 
		if nextChar is an opening parenthesis
			push nextChar onto the stack
		else if nextChar is a closing parenthesis
			pop the top of the stack
			if stack was empty or its top doesn't match the closing parenthesis
				balanced = false
				break
		idx = idx + 1
	return balanced

Postfix expression processor
E.g., 3 4 7 * 2 / +, its corresponding infix expression is 3 + ((4 * 7) / 2)

Queues (ADT | Array-based implementation | Linked Queue

Queue is a FIFO (First-In, First-Out) list, a list-like structure that provides restricted access to its elements: elements may only be inserted at the back and removed from the front.
Similarly to stacks, queues are less flexible than lists.
Enqueue: insert elements into queue at the back.
Dequeue: remove elements from the front.
The linked queue implementation is a straightforward adaptation of the linked list. However, array-based queues might be tricky to implement. A naive implementation will require $\Theta(1)$ time for each enqueue operation, and $\Theta(n)$ for each dequeue operation (because all of the elements must be shifted down by one position to retain the property that the remaining $n-1$ queue elements reside in the first $n-1$ position of the array; the "drifting queue" problem). Using a "circular" queue can solve the problem.

What's available in Java

Array: a data structure, which stores a fixed-size sequential collection of elements of the same type.
```
	int[] myInt = new int[10];
	myInt[0] = 10;
	double[] myDouble = {1.0, 3.5, 7.0};
```
List, ArrayList, LinkedList

Vector: a growable array of objects. A vector is similar to a traditional Java array, except that it can grow as necessary to accommodate new elements.

//Vector(int size, int incr)
//size: the initial capacity 
//incr: the increment size, the number of elements to allocate each time that a vector is resized upward
Vector<String> tweets = new Vector<String>(100, 20);

Stack (java.util.Stack)

public class Stack<E> extends Vector<E>

Queue (java.util.Queue)

public interface Queue<E> extends Collection<E>

Collection, Set, List
- A Collection represents a group of objects known as its elements.
- List in Java provides ordered and indexed collection which may contain duplicates.
- Set provides an un-ordered collection of unique objects, i.e. Set doesn't allow duplicates
  (image source)

Use Iterators (vs a loop)
An iterator can be used to cycle through the elements in a collection; it implements either the Iterator or the ListIterator interface. ListIterator extends Iterator to allow bidirectional traversal of a list, and the modification of elements.

List<String> words = new ArrayList<String>();
words.add("first");
words.add("second");
//use for loop
for(int i = 0; i < words.size(); i ++) 
	System.out.println(words.get(i));
//use Iterator
Iterator<String> it = words.iterator(); //create the intertor first
while(it.hasNext()) { //use while loop
	System.out.println(it.next());
}

Use Generics (<angle brackets>) and how it is different from casting

List <String> list = new ArrayList<String>(); //use generics
list.add("hello");
String s = list.get(0);

List list = new ArrayList();
list.add("hello");
String s = (String) list.get(0); //use casting