Introduction
Today in class we will illustrate the functionality of the Linked List, Stack, and Queue.
In this presentation we will cover the way a Linked List's various features work.
Watch the archived lecture on Canvas via Zoom - Cloud Recordings.
(After class on Tuesday is over.)
Linked Lists vs. Arrays
- A Linked List is linear, like an array, however it is made up of many linked nodes.
- Because we link Nodes with pointers as needed, we only allocate space for one item at a time - unlike an array, where we have to balance allocating enough space with not wasting too much space.
- With an array, we just declare an array of the data type we're storing:
TYPE* arr = new TYPE[SIZE]; - Since our linked list's nodes need to track its neighbors, the data and the neighbor pointers are all stored in a Node class, and then the LinkedList class stores pointers to the first/last Nodes.
LinkedList<TYPE> list;contains
Node<TYPE> * ptrFirstandNode<TYPE> * ptrLast
Node class
|
UML Diagram:
|
The Node class must contain the data to be stored, and at least the
pointer to the next Node. For our data structure we will also store
a pointer to the previous node. This makes our list a
Doubly-Linked List instead of a Singly-Linked List.
|
We can link nodes together without a linked list structure, but we create the LinkedList to act as the node manager and also provide a public "interface" of functionality (Push, Pop, Get).