View source for Lists Study Guide

=Definitions and Variations=

==Definitions==

'''list''' - an ordered collection of elements, not necessarily sorted, indexed to allow random access

'''vector''' - variation on a list (mathematical version of a list)

'''array list''' - a list implemented using an array, in which each element of the list is stored at a unique index

'''linked list''' - a list in which each element points to the next element, making insertion and deletion efficient at the cost of random access

'''iterator''' - a moving reference that walks through every item in the list in order

'''sentinel node''' - a linked list node that goes at the front and acts as a buffer, easing implementation of operations

'''head node''' - first node or element in a list

'''tail node''' - last node or element in a list

'''doubly-linked list''' - linked list in which each node contains two references, one to the preceding node and one to the successor node

'''nested class''' - common construct used to implement linked list nodes

'''circularly linked list''' - linked list in which last element points to first element, useful for applications involving cyclic order

'''cloning''' - produces a potentially shallow copy of the object (some objects implement cloning as a deep copy, but not all)

'''array list''' - list implementation that uses an array (usually dynamically resized) under the hood

=ADT and Interfaces=

==Basic List ADT==

The most basic list ADT is as follows:
* get 
* set 
* add 
* remove
* size 
* empty

==More Ornate List ADT==

A slightly more ornate list ADT is given by the following list:
* get
* set
* add - to front, to back
* remove - from front, from back
* size
* empty
* contains
* clear
* first
* last

==Java List ADT==

The Java List ADT provides a number of methods mentioned above, in addition to others:
* get
* set 
* add i
* remove i
* size
* empty
* contains
* clear

Plus other utility methods:
* indexOf
* sublist
* retainAll
* fill
* copy
* disjoint
* max/min
* replaceAll
* rotate
* shuffle
* sort
* swap

=Implementations=

Basically, the elements required in the class definition when we implement this data structure.

==Singly Linked List Implementation==

Node class:
* element - data
* next - reference
* constructor(e,n)
* get/set element
* get/set next

Linked List class:
* head pointer
* tail pointer
* size

==Circular Linked List Implementation==

Node class:
* element - data
* next - reference
* constructor(e,n)
* get/set element
* get/set next

Circularly Linked List class:
* tail pointer only
* size

==Doubly Linked List Implementation==

Node class:
* element (data)
* next - reference
* previous - reference
* constructor(e,p,n)
* get/set element
* get/set next
* get/set prev

Doubly Linked List class:
* header, trailer
* size

==Array List Implementation==

(No Node class)

Array List class:
* capacity - constant
* data - array, generic type
* size

=Algorithms for Operations=

==Singly Linked List Algorithms==

get(i) method:
* Deal with empty list case
* Start with pointer node equal to head node (element 0)
* Step forward i times (i is 0-indexed)
* Return list element at pointer node

set(i,e) method:
* Deal with empty list case
* Start with pointer node equal to head node (element 0)
* Step forward i times
* Replace element at pointer node

clear() method:
* Deal with empty list case
* Set head to null
* Update size

clone() method:
* Create new list
* (Shallow) copy items one at a time
* Return new list

equals() method:
* Check sizes are equal
* If size > 0, 
* Iterate through both lists, comparing each item
* Return false if any tests fail
* Return true at the end

addFront(e) method:
* Deal with empty list case
* Save current node to temp
* Set head to new node
* Set  temp to new head next
* Update size

addBack(e) method:
* Deal with empty list case
* (Assuming there is a tail pointer - otherwise, get it)
* Set tail next to new node
* Set tail to tail next
* Update size

removeFront() method:
* Deal with empty list case
* Set head to head next
* Update size

removeBack() method:
* Deal with empty list case
* Iterate to the pointer before tail (pretail)
* Set pretail next to null
* Set tail to pretail
* Update size

==Circularly Linked List Algorithms==

get(i)/set(i,e) methods:
* Deal with empty list case
* Start with pointer equal to tail next (element 0)
* Step forward i times (i is 0-indexed)
* Set/return list element at pointer node

addFront(e) method:
* Deal with empty list case
* Create new node
* Save tail next as temp
* Set tail next to new node
* Set new node next to temp
* Update size

addBack(e) method:
* Deal with empty list case
* Create new node
* Save tail next as temp
* Set tail next to new node
* Set new node next to temp
* '''Set tail to tail next''' - only operation different from addFront(e) method
* Update size

removeFront() method:
* Save tail next next as temp
* Set tail next to temp
* Update size

removeBack() method:
* Iterate to pointer before tail
* Set pretail next to tail next (i.e., set new tail to current head)
* Update size

==Doubly Linked List Algorithms==

Note: header and trailer are the leading and trailing sentinel nodes

get(i)/set(i) methods:
* If index > mid, use head++
* If index < mid, use tail--

addFront(e) method:
* Deal with empty list case
* Create new node
* Set new first's previous pointer to header, set next pointer to old first
* Fix header's link
* Fix old first's link
* Update size

add(i,e) method:
* Deal with empty case
* Create new node
* Set new node's previous pointer to node (i-1), set next pointer to node (i)
* Fix node (i-1)'s links
* Fix node (i, now i+1)'s links
* Update size

addBack(e) method:
* Deal with empty case
* Create new node
* Set new node's previous pointer to trailer's previous pointer, set next pointer to former last node
* Fix trailer's links
* Fix former last node's links
* Update size

removeFront() method:
* Store header next next in temp
* Set header next to temp
* Set temp previous to header
* Update size

remove(i) method:
* Store node i previous in pre
* Store node i next in post
* Set pre next to post
* Set post prev to pre
* Update size

removeBack method:
* Store trailer previous previous in temp
* Set trailer previous to temp
* Set temp next to trailer
* Update size

Can also utilize private/protected utility methods.

=Complexity and Cost=

=OOP Principles=



=Flags=

{{LinkedListsFlag}}

{{ArraysFlag}}

[[Category:StudyGuide]]