10.1 Relation between data structure and algorithms
An array and a linked list have different implementations for append an item and return the first item but can have the same implementations for return the current size
10.2 List abstract data type (ADT)
List: a common ADT for holding ordered data and having operations
Common operations for a list ADT: append, prepend, insert after, remove, contains, print, sort, is empty, get length
10.3 ArrayList ADT
Java Collection Framework (JCF): defines interfaces and classes for common ADTs known as collections in Java
Collection: represents a generic group of objects known as elements
Both an ArrayList and LinkedList are ADTs implementing the List interface
ArrayList offers faster positional access
LinkedList offeres faster element insertion and removal
NOTE: add(T) appends to the end and returns true if successful; add(int, T) inserts at the specified index and returns nothing
NOTE: set(int, T) replaces the element at the specified index and returns the previous element
NOTE: remove(int) removes by index and returns the removed element; remove(Object) removes by value and returns true if found and removed, otherwise false
To maintain a list in ascending sorted order, a given new item should be inserted at the position of the first element that is greater than the item
10.4 List data structure
A linked list is commonly implemented using two data structures:
- List data structure: manages the entire linked list by storing references to the head and tail nodes, and optionally the list’s size
- List node data structure: represents an individual element in the linked list, storing its data and pointers (references) to other nodes
10.5 Array-based lists
Array-based list: a list ADT implemented using an array
A length variable tracks how many array elements are in use
When the list length reaches the allocation size, the array is resized by allocating a new array with a larger capacity and copying the existing elements into it
NOTE: resizing commonly doubles the current allocation size
Prepend:
Insert-at: best: , worst:
Search returns index of first equal list item; returns -1 if not found
Search and remove-at: worst:
10.6 Singly-linked lists
First node: head
Last node: tail
NOTE: the list structure typically has pointers to the list’s first node and last node
A singly-linked list: a type of positional list in which each element contains a pointer to the next element.
NOTE: assign next pointer after next node creation
A list ADT implementation that uses a singly-linked list will have some functions that operate on list items and others that operate on singly-linked list nodes. Node-oriented functions handle the internal implementation, while item-oriented functions provide an interface for external code
10.7 Singly-linked lists: Search and insert
Search operation
Search operation returns the first node whose data equals that data value; returns null if no such node exists
Insert-node-after operation
Insert-after operation
NOTE: for insert-after operation, ifListSearch() returns null, ListInsertAfter() returns false without changing the list
10.8 Singly-linked lists: Remove
Remove-node-after operation removes current node if not null; removes first node otherwise
Removal causes an error when calling remove-node-after on empty list
Remove-item operation
10.9 Linked list traversal
a list traversal algorithm: visits all nodes in the list once and performs an operation on each node
Reverse traversal: vists all nodes starting with the list’s tail node
10.10 Linked list dummy nodes (optional)
10.11 List: LinkedList
The LinkedList: an ADT implemented as a generic class that supports different types of elelmtns
NOTE: set(int, T) replaces the element at the specified index and returns the previous element
NOTE: add(T) appends to the end, add(int, T) inserts at the specified index
NOTE: remove(int) removes by index and returns the removed element; remove(Object) removes the first matching element and returns true if removed, otherwise false
A ListIterator: an object that points to a location in a List and provides methods to access an element and advance the ListIterator to the next position in the list. Located between two elements in a list
ListIterator:
hasNext(): returns true if there is a next element; false otherwisenext(): returns the next element in the list and moves the ListIterator to the next locationadd(): adds new element between the next and previous elements and moves the ListIterator after the new elementremove(): removes the element returned by the prior call tonext()orprevious()set(): replaces the last element accessed by the iterator
NOTE: LINKEDLIST AND ARRAYLIST ARE ADTS IMPLEMENTING THE LIST INTERFACE
10.12 Enhanced for loop
Enhaced for loop: for loop that iterates through each element in an array or Collection
Compile-time type inference for local variables
for (var i = 0; i < grades.size(); i++) System.out.println(grades.get(i));
for (var g : grades) System.out.println(g);10.13 Linked lists: Recursion
10.14 Doubly-linked lists
A doubly-linked list: a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node
Append operation
NOTE: ListAppend() allocates a new doubly-linked list node and assigns the new node’s data with the item parameter
Prepend operation
10.15 Doubly-linked lists: Search and insert
Search operation
Insert-node-after operation
NOTE: insert-node-after operation assumes the current node is valid if the list is non-empty
Insert-after operation (for items instead of nodes)
NOTE: insert-after operation does nothing if the current node not found
10.16 Doubly-linked lists: Remove
Remove-node operation
NOTE: remove-node assumes the current node is valid and belongs to the list
Remove-item operation
NOTE: remove-item operation does nothing if the node to remove not found
10.17 Circular lists
A circular list: a linked list where the tail node’s next pointer points to the head of the list, instead of null
The head of a circular linked list is often referred to as the start node