Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM09 Lists, Stacks, and Queues - Coggle Diagram
MM09
Lists, Stacks, and Queues
Lists
List Basics
Position - Most Important Concept
First, Second ..., n element
Finite, ordered sequence of elements
not sorted
Embodying Math sequences
Each list element has a data type
But not all elements need to be the same
Ops don't depend on the "elemental data type"
Head - Beginning
Tail - End
Beginning position = 0
Number of elements = Length of list
Sorted and Unsorted lists
Implementing a List ADT
Consider basic operations
Grow and Shrink
Insert and
Remove elements
From anywhere in the list
Gain acess to a value
Read or change it
Create new lists
Clear lists (delete all elements)
Find next and previous value
Define ADT as a set of
operations on the List object
Abstract Class for definition of list ADT
Defines member functions to be inherited
Does not specify operations
Math Sequence as a base
Acess to any position
Inserting - Removing
Moving to x pos
Acess to n+1/n-1 pos
next - prev
n + 1 current positions
Reading value - can't receive null
Array Based List Implementation
Inherits from abstract class List
Must implement all member functions
Maximum size has to be specified
If less than max, it's current value is stored in list size
Default Size can be set a default constant
Random acess is easily implemented
Insert and Remove - shifts other values of the list - more time to process O(n)
Linked Lists
Dynamic Memory Allocation
Allocates memory for new elements
Pointers
Nodes
Distinct object
Separate class for ListNodes
Useful for Stack/Queue DS
Element - Next
Element = Value
Next = ptr to next node
Singly Linked List - One-Way LL
First and Last elements
Pointers to head and tail
List Size stored explicitly and updated for every op
Current element - Pointer curr
Representing current position
Pointer to the element (n-1) before curr