Unit 14: Linked Lists

  1. Introduction
  2. Linked lists vs. arrays
  3. Node class
  4. Linked list class
  5. Functionality of a Linked List

  6. Example code and additional resources

This week's stuff:

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> * ptrFirst and Node<TYPE> * ptrLast

Node class

UML Diagram:

Node
- data : TYPE
- ptrPrev : Node<TYPE>*
- ptrNext : Node<TYPE>*

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.

(Note that the names of variables/classes here might not match 1:1 to the code lab. You should be able to infer what is what based on similar names.)

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).

Linked list class

UML Diagram:

LinkedList
- itemCount : size_t
- ptrFirst : Node<TYPE>*
- ptrLast : Node<TYPE>*
+ LinkedList()
+ ~LinkedList()

+ PushFront( newData: TYPE )
+ PopFront() : void
+ GetFront() : TYPE&

+ PushBack( newData: TYPE )
+ PopBack() : void
+ GetBack() : TYPE&

+ PushAt( index: size_t, newData: TYPE )
+ PopAt( index: size_t ) : void
+ GetAt( index: size_t ) : TYPE&

The LinkedList class contains a pointer to the first node (aka "head") and the last node (aka "tail"), and we can also include an item count so that we don't have to "count" all the nodes every time we want to grab the size.

(Note that the names of variables/classes here might not match 1:1 to the code lab. You should be able to infer what is what based on similar names.)

Functionality of a Linked List

If I added the same information about Linked List functionality here as I have in the book, pretty soon the data between both sources would go out of sync and I don't want to have to maintain two separate resources on this. Therefore, it's time to pop over to the book. ;)



➡️➡️ https://moosadee.gitlab.io/courses/ ⬅️⬅️

Example code and additional resources

Videos: