Quick Index
Overview


We'll look at adding elements to a linked list.

Adding First Node


Let us look at the case when the list is empty (has no elements).

We'll look at an example where we add an element to the empty list.

We'll see that "addFirst" and "addLast" will do the same thing for this case.

Before
Before the add action.

The linked list is empty -- both ivars ("firstNode" and "lastNode") are null.
After
After the add action.

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

Notes:
  • The new node's links are null
  • both ivars ("firstNode" and "lastNode") point to the new node


Method 'addFirst'


It is not uncommon for a problem to require adding to the start of a list. Recall that this is an inefficient operation for a dynamic array (requires shifting).

We'll assume the linked list is not empty (before the add). In other words, the pre-condition is the list has one or more elements.

Algorithm Concept
We can see (in red) that little work needs to be done to add data to the front of the list.

Let the special object "this" be a linked list.

At a high level:

  • Construct new node (Blaine)
  • Set link from BP to Blaine
  • Set link from Blaine to BP
  • Set "this.firstNode" to Blaine
  • Increment list size
Algorithm Pseudocode
The algorithm is shown.

Basically it's link pointer housekeeping logic.
Algorithm:

let this = the linked list



Method 'addLast'


The logic for "addLast" is similar to "addFirst".

We'll assume the linked list is not empty (before the add). In other words, the pre-condition is the list has one or more elements.

Algorithm Concept
We can see (in red) that little work needs to be done to add data to the end of the list.

Let the special object "this" be a linked list.

At a high level:

  • Construct new node (Blaine)
  • Set link from NH to Blaine
  • Set link from Blaine to NH
  • Set "this.lastNode" to Blaine
  • Increment list size
Algorithm Pseudocode
The algorithm is shown.

Basically it's link pointer housekeeping logic.
Algorithm:

let this = the linked list



Method 'set'


ADT
The ADT method description
set(index, newElem);
	/*
	Insert passed arg "newElem" into position "index"
	Return previous (replaced) elem at "index"
	Valid "index" values are between 0 and "size - 1"
	If "index" is invalid, throws exception:
		"(set) Index %d is out of bounds"
	*/
Algorithm
What is the algorithm for "set"?


Let us copy (and tweak) the traversal logic from the "get" method.

At the point we find the node (where "get" returns the data) we'll instead do this:

node.setData(newElem);


Method 'addAll'


From the ADT:

addAll(otherDynList);
	/*
	Add (append) all elements from "otherDynList" into "this" list.
	The newly added elements will retain their order (as they have in otherDynList)
	All existing elements are preserved and will precede (be before) the newly added elements.
	No return value.
	*/

This one is a "gimme" (very easy).

It's all reuse.

We simply loop over "otherDynList" and for each element we call "this.add" with the element.




































Data Structures And Algorithms (DSA) (Chapter 401 - Linked List Logic)










Chapter 401 - Linked List Logic Adding

Contents Intro OO Review Concepts Design Traversal Algorithms Memory

Chapter Top Search TOC