Quick Index
Index
Videos


A video on this chapter is here....

Overview


Visual
Here is a quick visual of a linked list. As we can see, we have a list of data elements linked (chained) together.

Pure Object Work
This linked list is a fun object to work with.

It's pure objects!


Keep it Simple 💡


Key information is here: context and scope...

Reduce things to the simplest possible context (universe).

For example, when studying/analyzing "Node", focus only on it and do not worry about the linked list.

Abbreviations


The following abbreviations will be used in the examples:

Term/ElementWhich Means
nodeDoubly linked node
Linked ListDoubly linked list
LLLinked List
single links in diagramsSome diagrams show forward "next" links. If not shown, backward "prev" links are implied.
nextA link from a node to the "next" node. Also called "forward link".
prevA link from a node to the "prev" node. Also called "backward link".
linkanother term for "next" or "prev"
pointeranother term for "next" or "prev"


Note: There is also a structure called a "singly linked list" but a doubly linked is generally preferred so we will focus on it.

Concept


A linked list is a structure with nodes linked together. Each node holds onto data.

Links are simply regular "variables" that hold another node (e.g. the next node or previous node).

Linked List Schematic
This sketch just gives us a conceptual idea of what a linked list looks like. Do not worry about details yet.
Simplified
We'll be hiding the backward links in many cases just to simplify the diagrams (it is symmetric).

We'll remember the backward links are implied.
Non-Contiguous Memory
Unlike arrayed structures, link list nodes are not in contiguous memory.

Note -- We will find out that this fact has some pros and cons regarding performance.
Linked List Whiteboard
For scratching out your ideas.
Right-Click "Save image as"
Open image and sketch on it

Nodes 💡


Overview


Here is a video on this section...

Nodes are the building blocks of linked lists (and many other data structures).

Concepts (and Structure)


Node Has Data
The primary job of a node is to hold onto data (an object). This data may be any type -- City, Person, etc.
Node Has Links
Nodes have two links. One like to the previous node, and one to the next node.

This allows list navigation.
Complete Node
Here is the complete Node. It is doubly linked and holds data.
Node Whiteboard
For scratching out your ideas.
Right-Click "Save image as"
Open image and sketch on it


Examples - With Data


Node With City Data
This node has a City object.
Node With Person Data
This node has a Person object.
Node With Integer Data
This node has an Integer object.


End Nodes


First Node
The first node is like any other node except that it's "prevNode" link is null.
Last Node
The last node's "nextNode" link is null.

Linked List


Overview


A linked list provides the services specified on the DynamicList ADT

The core input methods like "addLast", "addFirst", will receive a "data" object parameter. For example if we have a linked list of City objects, then the linked list would expect a message sent to it like "addFirst(aCity)".

Behind the scenes the linked list would use nodes to hold this data. The example actions in the next section will show these mechanisms in detail.

Concepts


Object Structure
The linked list only has to keep track of two things (shown in red):

  • firstNode
  • lastNode
Empty (Size Zero)
It is helpful to visualize and understand the initial or "empty" list.
Size One
List with one element.
Size Many
List with many elements.

Traversing a Linked List


Overview


A linked list has "firstNode". Thus we can start with it, and then "traverse" (walk) through all the nodes.

We can also start at "lastNode" and traverse in reverse or back through the list.


Prep for Traversal (Loop)


Assign the firstNode to a temporary variable. We can call it anything -- let's use "visitedNode".

"this" is the linked list we are coding in.

visitedNode = this.firstNode


Traversing (Looping)


Visit Node1
We can now "visit" this node doing whatever we like (in the loop code block).

Increment a count, print, etc.

We can get the visited element via "visitedNode.getData()"
While not at end {
	CODE BLOCK
	E data = visitedNode.getData();
}
Move to Node2
visitedNode = visitedNode.getNextNode();

We are now at "Node2".

And we can again do what we need to do during this "visit" (in loop code block)
Move to Node3
visitedNode = visitedNode.getNextNode();

We are now at "Node3".

And again we "visit" how we like.
The End
visitedNode = visitedNode.getNextNode();

Node3's next node is null.

We have reached the end.


The Recipe



visitedNode = this.firstNode
While (visitedNode != null) {
	Do Whatever
	visitedNode = visitedNode.getNextNode()
}

Adding/Inserting/Removing


addFirst and addLast (Empty/Initial List Case)


Before
Before the add action.
After
After the add action.

We have constructed a new node with data City "Blaine":

  • New node's links are null
  • LinkedList's firstNode points to new node
  • LinkedList's lastNode points to new node


addFirst (Non-Empty List Case)


Work for 'addFirst'
Algorithm:

let o = the old first node
let n = the new first node

  • o = get linked list's first node
  • n = construct new node on new data
  • o.setPrevNode(n)
  • n.setNextNode(o)
  • set linked list first node = n


addLast (Non-Empty List Case)


Work for 'addLast'
Algorithm:

let o = the old last node
let n = the new last node

  • o = get linked list's last node
  • n = construct new node on new data
  • o.setNextNode(n)
  • n.setPrevNode(o)
  • set linked list last node = n


Inserting


insert Schematic
The red shows "work" needed to insert node into the list.

  • Create new node and give it the data (object)
  • Do housekeeping on links as shown
insert (large list)
As the list size increases the "work" (red) remains constant as shown.

Question -- How does the work compare with the work required for DynamicArray's insertions?


removeFirst


Before
We are about to remove the first node (BP)
After
The red shows "work" done for removeFirst.

The work consisted only of link housekeeping.

Question -- How does the work compare with the work required for DynamicArray's removeFirst?
removeFirst Whiteboard
For scratching out your ideas.
Right-Click "Save image as"
Open image and sketch on it

Getting


Overview


We'll go over getting the first or last data items in the list here. A following section will look at how to get a data item at a given index.

Remember: Pretend to "be" the LinkedList in this section.

Examples


Return Data (Not Node)
Let us our list is being used to hold "City" data.

Say our list is of size one and has one City data object ("Brooklyn Center").

The object user will expect to get the City object "Brooklyn Center" returned when they do "get", "first" , etc.

They are not interested in our nodes.

Fortunately, for or us to get data given a node is trivial (i.e. "getData").
first
From the previous sketch we know how to get data from a node.

Then how would we return "first"? For the example shown, how would we return the City object "BP"?
last
How would we return "last"? For the example shown, how would we return the City object "NH"?

Algorithm For Indexed Access


Here is a companion video for this section.

Problem: We need to come up with an algorithm recipe for getting an element at a given index.

Algorithms are pseudo code (not real code). Algorithms generally convert nicely to real code.

Try 1 - Algorithm Recipe
  • Start a count at 1
  • Move (navigate) down the list
  • Increment the count as we move from node to node
  • When count is equal to the specified index, we are done (return the data in that node)
Recall Linked List Concept Sketch
Note that in the context of the linked list, we only have "firstNode" and "lastNode". This is good -- nice and simple.
Key Player: Our Little Node
Let's recall our wonderful little node.

She has three components: nextNode, prevNode, and data.
Try 2 - Improved Algorithm Recipe
Given our review of linked list and node, we will add a little detail to our algorithm recipe. Note that we are coding in a linked list (that is our context).

given "index" (the pos to access)
count = 0
node = firstNode
While node is not null
	if (count equals index)
		Return the node's data
	node = node.getNextNode()
	Increment count

Add In Exception Cases
Now we'll handle exception cases.

As the first step in the algo recipe we would add something like:

  • Check if the given index is a valid index
  • If invalid we would handle the case as the problem write-up dictates (e.g. throw exception, return null, etc)

Algorithm For Computing Size


This algorithm computes the size of list.

We'll leverage (use) our previous algorithm (for indexed access) and modify it a little for size. All our algo recipes for list iteration will follow a similar pattern.

Note that we may optimize the linked list 'size' method by tracking size and storing it in a variable. We will not worry about that here.

Recall Previous Algorithm
Algorithm for getting data at given index.

given "index" (the pos to access)
count = 0
node = firstNode
While node is not null
	if (count equals index)
		Return the nodes data
	node = node.getNextNode()
Algorithm Modified to Compute List Size
count = 0
node = firstNode
While node is not null
	Increment count
	node = node.getNextNode()
Return size

Modeling (Coding) Tips



References
































Coding Fundamentals (Chapter 306 - IntroLinkedListWithAlgos)










< - Introducing Linked List With Algorithms >

Search Site Home Back To Top