Table of Contents

1. Coming from arrays…

arrays.png

Before taking a Data Structures course, you've probably only managed data in your program via arrays.

When we declare an array in C++, we must give it a size (whether we're making a dynamic array or a vanilla array). This ensures that memory can be allocated so that each element of the array is side-by-side with other elements.

Investigating arrays and memory addresses

Let's write a simple program to look at how arrays are stored in memory, in case you don't remember.

First, how big is one element? We can use the sizeof function to find out how big, in bytes, a given data type is:

cout << "The size of a int is: "
     << sizeof( int ) << " bytes." << endl;
The size of a int is: 4 bytes.

One integer is 4 bytes. Next, we can declare an array of integers and look at how many bytes that takes up:

const int SIZE = 10;
int intArr[SIZE];
cout << "Size of a int array with "
     << SIZE << " elements: "
     << sizeof( intArr ) << " bytes." << endl;
Size of a int array with 10 elements: 40 bytes.

Now, let's look at the memory addresses of each element:

cout << "Memory addresses for the int array:" << endl;
for ( int i = 0; i < SIZE; i++ )
{
    cout << "Element " << i << ": " << &(intArr[i]) << endl;
}
Memory addresses for the int array:
Element 0: 0x7ffff9867d00
Element 1: 0x7ffff9867d04
Element 2: 0x7ffff9867d08
Element 3: 0x7ffff9867d0c
Element 4: 0x7ffff9867d10
Element 5: 0x7ffff9867d14
Element 6: 0x7ffff9867d18
Element 7: 0x7ffff9867d1c
Element 8: 0x7ffff9867d20
Element 9: 0x7ffff9867d24

Each time this program runs, we will have different memory addresses for the intArr, but those addresses will always be contiguous in memory, 4 bytes apart.

contiguousarray.png

Sidenote 1: Hexadecimal
When we write in hexadecimal, we want each number to only take up one character space. So, we have 0-9 to be 0 through 9, but then 10 is A, 11 is B, 12 is C, 13 is D, 14 is E, and 15 is F.
Sidenote 2: Address of the beginning of the array
The address of intArr is the same as the address of intArr[0].

Pros and Cons of arrays for storing data

Pros:
  • Random access is instant: This means, we can access an element at any arbitrary index instantaneously. How? Well, we have the address of the 0th element, and to get an item at position \(i\), we just have to add i * sizeof(int). A simple math operation is virtually instant. AddressOf( i ) = AddressOf( 0 ) + i * sizeof( dataType )
Cons:
  • Resizing a dynamic array is costly: Any time our array is full, to resize it we have to allocate memory for a new array of a bigger size. Then, we have to copy each element from the old array to the new array. This takes time any time resize occurs.
  • We have to over-estimate the array size: We don't want to have to resize the entire array every time a new item is inserted, so we generally will resize it by some quantity each time (not just adding 1 to the size of the array). This means we're allocating more space than we're actually using if the array isn't full.

The study of Data Structures is all about the trade-offs between different data types: Some are faster to access data but slower to insert new data and vice versa. Instead of storing data in an array-based structure, we can make a tradeoff of less memory used, instant insertion of new data in exchange for slower access using a linked structure.

A dynamic array:

dynamicarray.png

A linked list:

linkedlist.png

Review 1. Arrays are fast at _ and, over time, arrays are somewhat slow at _.

(a) Random access, (b) Adding new data

Review 2. Arrays are not space-efficient because…

○ We have to over-estimate how much space will be needed; there will (almost) always be unused spaces.

○ We only allocate space for one element at a time, linking it back to its previous and next items.

Review 3. If you didn't over-estimate the size of an array, only allocating exactly as much memory as you need at a given time, then your performance would tank because…

○ Every insert requires a resize, which is slow.

○ Every insert requires updating pointers "ptrNext" and "ptrPrev", which is slow.

2. LinkedNode structure - Wrapping the data and storing neighbor pointers

A drawing of two nodes pointing at each other.

Figure 1: A drawing of two nodes pointing at each other.

The Node is one of the two structures we build when implementing a linked list or other linked type structure. The node is responsible for storing the data itself, and storing one or more pointers.

Singly-linked List's Nodes

A drawing of nodes A, B, and C, each node only pointing to its next neighbor.

Figure 2: A drawing of nodes A, B, and C, each node only pointing to its next neighbor.

With a singly-linked list, the nodes only point to the next Node after them. These nodes don't know what comes before each of themselves.

SinglyLinkedNode  
- data : TYPE
- ptrNext Node<TYPE>*
template <typename T>
struct Node {
public:
  Node();
  Node<T>* ptrNext;
  T data;
};
Doubly-linked List's Nodes

A drawing of nodes A, B, and C, each with arrows pointing to the next and previous items.

Figure 3: A drawing of nodes A, B, and C, each with arrows pointing to the next and previous items.

With a doubly-linked list, the nodes point to both the next Node and the previous Node.

DoublyLinkedNode  
- data : TYPE
- ptrPrev Node<TYPE>*
- ptrNext Node<TYPE>*
template <typename T>
struct Node {
public:
  Node();
  Node<T>* ptrNext;
  Node<T>* ptrPrev;
  T data;
};

Warning! Remember that any class with pointers in it should be setting those pointers to nullptr in its constructor!

A Node is simple enough that you could implement it as a struct instead of a class, but it's up to you. A Node is only used by the List (or linked structure) itself, the user wouldn't be accessing the Node or even know about it.

Single vs. Double?

I generally prefer to teach how to implement a doubly-linked list first, because the functionality is easier to implement when each Node is aware of what comes before itself.

Once you understand how a doubly-linked list works, you can figure out a singly-linked list; it just means having to iterate through the list more often.

  1. The Node structure contains…
  • ○ Data, pointer to first node of list, Pointer to last node of list
  • ○ Data and at least one pointer to a neighbor
  • ○ Just data
  • ○ Just pointers
  1. Identify each of the following items:

node_with_ptrNext.png]]

node_with_ptrPrev_and_ptrNext.png]]

  1. When a new Node is instantiated its pointers need to be

initialized to a safe value. Which of the following represents a properly initialized Node?

node_with_ptrPrev_and_ptrNext_to_self.png]]

node_with_ptrPrev_nullptr_and_ptrNext_nullptr.png]]

node_with_ptrPrev_and_ptrNext_to_LinkedList.png]]

3. List class functionality

list-and-node.png

The List class itself is what handles interfacing with the "user" (or other programmers using your List). Data Structures generally will have Access, Add, Remove, and Search functionality, and those functions (and helper functions) are stored in our List.

The List will also keep track of the first Node in the list, and often also the last Node by storing Node* pointers. (You could get by without the last Node pointer, but it's just easier, dude.)

The list is also responsible for the memory management - it will allocate memory for a new Node when it's needed, and free the memory of a Node when it's to be removed.

delete-node.png

3.1. Member variables of a DoublyLinkedList

If we're building a Doubly Linked List this means that our Nodes will keep track of pointers to their previous and next neighbors. For the List itself, we need at minimum a pointer to the FIRST Node in the list, but we could also store a pointer to the LAST Node in the list as well to make implementation simpler.

For our DoublyLinkedList we will have private member variables ptrFirst and ptrLast, which are both Node pointers. Each Node will include its own data, as well as a ptrPrev pointer and a ptrNext pointer. If a Node doesn't have a neighbor in a direction, then that pointer is set to nullptr.

An empty LinkedList will begin with its ptrFirst and ptrLast both pointing to nullptr.

linkedlist-empty.png

Figure 4: A LinkedList with its ptrFirst and ptrLast both pointing to nullptr.

A LinkedList with one item will have both ptrFirst and ptrLast both pointing to the single Node.

linkedlist-1node.png

Figure 5: A LinkedList with a single node. The ptrFirst and ptrLast pointers from the LinkedList are both pointing to its single Node.

And as we get more and more Nodes, our LinkedList still only tracks the first and last Nodes - it is then up to each Node to keep track of its neighbors. The LinkedList only knows about its first and last Nodes! (And in some implementations, not even the last one!)

linkedlist-3nodes.png

Figure 6: A box representing LinkedList and three boxes representing Nodes with data "A", data "B", and data "C". LinkedList's ptrFirst is pointing to the "A" node, and its ptrLast is pointing to the "B" node. "A" node's ptrPrev points to nullptr, and its ptrNext points to node "B". "B" node's ptrPrev points to node "A", and its ptrNext points to node "C". "C" node's ptrPrev points to node "B", and its ptrNext points to nullptr.

Managing this structure comes down to adding, removing, and updating these pointers, as well as allocating memory for new Nodes when new data is added, and deallocating memory for Nodes once they get deleted.

Let's look at how a LinkedList works graphically before we jump into the code.

3.2. Getting data

Let's say we're starting with a LinkedList that has several Nodes.

initiallist.png

How do we access any given Node in the list? The Front of the list corresponds to ptrFirst and the Back of the list corresponds to ptrLast - we have pointers to both of these Nodes from the LinkedList itself. If we want a Node somewhere in the middle, we will have to do a bit more work.

3.2.1. GetFront()

Access the LinkedList's ptrFirst, then grab the data from there, returning ourList->ptrFirst->data.

linkedlist-ptrfirst.png

Figure 7: A LinkedList with the pointer to ptrFirst and the last Node highlighted.

3.2.2. GetBack()

Access the LinkedList's ptrLast, then grab the data from there, returning ourList->ptrLast->data.

linkedlist-ptrlast.png

Figure 8: A LinkedList with the pointer to ptrLast and the last Node highlighted.

3.2.3. GetAt( index )

This function will take in an index position. We will have to start at the ptrFirst Node and then traverse forward however many times until we get to that index.

We will need to create our own Node pointer to help us do this, starting it at the ptrFirst Node. In the code, this would look like Node* ptrWalker = ourList->ptrFirst. We're not allocating memory! This pointer is just for pointing!

linkedlist-walker.png

Figure 9: A Node* ptrWalker that has been initialized to the list's ptrFirst Node.

Once it's initialized, we would create a loop that counts up to the index given. Each iteration in the loop, we move the walker forward by accessing the pointed-to-Node's ptrNext. Code-wise, it looks like this: ptrWalker = ptrWalker->ptrNext.

linkedlist-walker2.png

Figure 10: ptrWalker is now pointing to the Node pointed to via ptrFirst's ptrNext.

Once we've looped the appropriate amount of times our walker pointer is at the location of the data we want, so we would then return ptrWalker->data.

3.3. Pushing new data

3.3.1. Pushing the first item in the list

Whether you're adding new data at the front or back of the list, the steps are the same for the very first item. We start with an empty LinkedList:

emptylist.png

Figure 11: A LinkedList with its ptrFirst and ptrLast both pointing to nullptr.

We allocate space for a new Node and set up its data:

newnode.png

Figure 12: A LinkedList with its pointers still set to nullptr, but a newNode object created and data set. The newNode's ptrPrev and ptrNext is nullptr.

Then we update the LinkedList's Node pointers to this new Node:

newnode2.png

Figure 13: The LinkedList has been updated so that its ptrFirst and ptrLast pointers are both pointing to the newNode.

If we're adding a new Node to a non-empty list, then we need to decide how to handle it based on the position where we're adding the new data: Front, back, or somewhere in the middle?

3.3.2. PushFront( newData )

Our LinkedList already has a few items added to it:

linkedlist-3nodes.png

Figure 14: A LinkedList. Its ptrFirst is pointing to Node A and its ptrLast is pointing to Node C. Node A's next is Node B. Node B's next is Node C. Node C's prev is Node B. Node B's prev is Node A.

Our new Node is going to be at the ptrFirst location, but we need to also update the pointers from the new Node to Node A (the "old-first"), and then update the LinkedList's ptrFirst.

pushfront.png

Figure 15: A LinkedList. Its ptrFirst is Node X. NodeX's next is Node A. Node A's prev is Node X.

3.3.3. PushBack( newData )

Our LinkedList already has a few items added to it:

linkedlist-3nodes.png

Figure 16: A LinkedList. Its ptrFirst is pointing to Node A and its ptrLast is pointing to Node C. Node A's next is Node B. Node B's next is Node C. Node C's prev is Node B. Node B's prev is Node A.

Our new Node is going to be at the ptrLast location, but we need to also update the poitners from the new Node to Node C (the "old-last"), and then update the LinkedList's ptrLast.

pushback.png

Figure 17: A LinkedList. Its ptrLast is Node X. NodeX's prev is Node C. Node C's next is Node X.

3.3.4. PushAt( newData, index )

Our LinkedList already has a few items added to it:

linkedlist-pushat-01.png

Figure 18: A LinkedList with four Nodes: A, B, C, and D. The List's first is Node A, and its last is Node D.

We want to add some new data at some index. For example, n. First we need to use a Walker pointer to iterate n times to get to the spot we need.

linkedlist-pushat-02.png

Figure 19: Nodes A, B, C, and D are neighbors. The Walker pointer is pointing to Node C.

This is where the new data will live. We can allocate space for the new Node, but we also need to update the neighbors. We want the Node before the walker to be X's (newNode's) previous, and the Node at the walker to be X's next, where our new Node X is taking the index from where the walker is at.

We could create another pointer to point to walker->ptrPrev, so that setting up all the neighbors will be easier, but this is optional:

linkedlist-pushat-03.png

Figure 20: The List with nodes A, B, C, and D. The Before pointer is pointing to Node B. The Walker pointer is pointing to Node C.

We can then place our new Node in the position between the walker->ptrPrev and the walker, updating the three Nodes' neighbor pointers:

linkedlist-pushat-04.png

Figure 21: The List's Nodes have been updated to A, B, X, C, and D. X is between B and C.

Using the "Before" alias pointer, our neighbor updates are:

  • before's ptrNext is newNode
  • newNode's ptrPrev is before
  • newNode's ptrNext is walker
  • walker's ptrPrev is newNode

Or, without the "Before" alias pointer, our neighbor updates are:

  • walker->ptrPrev's ptrNext is newNode
  • newNode's ptrPrev is walker->ptrPrev
  • newNode's ptrNext is walker
  • walker's ptrPrev is newNode

3.4. Popping data

3.4.1. Popping the last item

If our LinkedList has only one Node left, then the functionality for removing that Node will be the same no matter whether we're accessing it from the "ptrFirst" or "ptrLast".

We have our List with one Node:

linkedlist-1node.png

Figure 22: A List with its ptrFirst and ptrLast both pointing at the same single Node.

We delete that Node, either via our List's ptrFirst or ptrLast (doesn't matter which), then reset the ptrFirst and ptrLast pointers back to nullptr:

emptylist.png

Figure 23: A List with its ptrFirst and ptrLast both pointing to nullptr.

3.4.2. PopFront( newData )

Here our LinkedList already has a few items in it:

linkedlist-3nodes.png

Figure 24: A LinkedList. Its ptrFirst is pointing to Node A and its ptrLast is pointing to Node C. Node A's next is Node B. Node B's next is Node C. Node C's prev is Node B. Node B's prev is Node A.

Removing the Front of the List means we want to delete the Node that the List's ptrFirst is pointing to. However, before we do that, we need to set a new First (First's ptrNext), and then make sure our new First Node's ptrPrev is reset to nullptr.

popfront.png

Figure 25: LinkedList's ptrFirst is pointing to Node B and Node B's ptrPrev is pointing to nullptr. Node A is shown crossed out, as it gets deleted.

3.4.3. PopBack( newData )

Here our LinkedList already has a few items in it:

linkedlist-3nodes.png

Figure 26: A LinkedList. Its ptrFirst is pointing to Node A and its ptrLast is pointing to Node C. Node A's next is Node B. Node B's next is Node C. Node C's prev is Node B. Node B's prev is Node A.

Removing the Back of the List means we want to delete the Node that the List's ptrLast is pointing to. However, before we do that, we need to se a new Last (Last's ptrPrev), and then make sure our new Last Node's ptrNext is reset to nullptr.

popback.png

Figure 27: LinkedList's ptrLast is pointing to Node B and Node B's ptrNext is pointing to nullptr. Node C is shown crossed out, as it gets deleted.

3.4.4. PopAt( newData, index )

Here our LinkedList already has a few items in it:

linkedlist-3nodes.png

Figure 28: A LinkedList. Its ptrFirst is pointing to Node A and its ptrLast is pointing to Node C. Node A's next is Node B. Node B's next is Node C. Node C's prev is Node B. Node B's prev is Node A.

Let's say we want to get rid of the middle node, Node B. We will again need a Walker pointer to walk to this location. This is the Node that we want to delete, but we need to update Walker's previous Node's neighbors and Walker's next Node's neighbors.

popat.png

Figure 29: The list with Nodes A, B, and C, and the Walker pointer is pointing to Node B.

We can again create alias pointers, or work through the Walker itself.

popat2.png

Figure 30: The list with Nodes A, B, and C. Before pointer is pointing to Node A. After pointer is pointing to Node C. Walker pointer is pointing to Node B.

We update the Node's neighbors:

  • before's ptrNext is after
  • after's ptrPrev is before

Or, using just the Walker and not the alias pointers:

  • walker->ptrPrev's ptrNext is walker->ptrNext
  • walker->ptrNext's ptrPrev is walker->ptrPrev

Then we can delete the middle node via the Walker: delete ptrWalker;

popat3.png

Figure 31: Node B, pointed to by the Walker pointer, is crossed out as it is deleted. Node A's next is Node C. Node C's previous is Node A.

3.5. Error checks to keep in mind

As we're working on this structure we also need to keep a few error checks in mind, and throw exceptions in these cases:

  • For the Get functionality, if the List is empty we can't return anything!
  • For the Pop functionality, if the List is empty we can't remove anything!
  • For the At functionality, you need to check that the index passed in is valid - should be 0 or greater, and should be less than the node count.

Review 7. The _ class contains functionality to Add, Remove, and Access data.

○ Node / ○ List

Review 8. Which is which?

  • (a) Has ptrFirst and ptrLast:

    ○ Linked List / ○ Node

  • (b) Has ptrPrev and ptrNext :

    ○ Linked List / ○ Node

Review 9. Given this list:

linkedlist-3node-small.png]]

  • a. If we access list->ptrFirst->data, we will get back:
  • b. If we access list->ptrFirst->ptrNext->data, we will get back:
  • c. If we access list->ptrFirst->ptrNext->ptrNext->data, we will get back:
  • d. We can access "C" via:

    ○ GetBack() / ○ GetFront() / ○ GetAt(1)

  • e. We can access "A" via:

    ○ GetBack() / ○ GetFront() / ○ GetAt(1)

  • f. We can access "B" via:

    ○ GetBack() / ○ GetFront() / ○ GetAt(1)

Review 10. Starting with this list:

linkedlist-3node-small.png]]

Identify which operation represents a call to which function:

LL-small-ABCX.png]]

LL-small-AXBC.png]]

LL-small-XABC.png]]

LL-small-AB.png]]

LL-small-AC.png]]

LL_small-BC.png]]

4. Implementing a Doubly-Linked List

4.1. Structure of a DoublyLinkedList's Node

Start by creating a DLinkedList.h file. We can declare our Node for our Doubly Linked List at the top of this file, which will look like this:

DLNode  
+ data : TYPE
+ ptrNext : DLNode<TYPE>*
+ ptrPrev : DLNode<TYPE>*
+ DLNode()  
+ DLNode( newData : T )  
#ifndef _DLINKEDLIST
#define _DLINKEDLIST

#include <stdexcept>
using namespace std;

template <typename T>
struct DLNode
{
    DLNode();
    DLNode( T newData );

    T data;
    DLNode<T>* ptrPrev;
    DLNode<T>* ptrNext;
};

#endif

4.2. DLNode's Constructor

  • The Node's constructor is responsible for setting the pointers to nullptr for safety!

Since we're working with templates here our function definitions need to go in this .h file as well - no .cpp file! Define the Node's constructor beneath the declaration.

template <typename T>
DLNode<T>::DLNode()
{
    ptrPrev = nullptr;
    ptrNext = nullptr;
}

template <typename T>
DLNode<T>::DLNode( T newData )
{
    data = newData;
    ptrPrev = nullptr;
    ptrNext = nullptr;
}

4.3. Structure of our DoublyLinkedList

And within a DLinkedList.h file, we will create our Doubly Linked List's class declaration:

DoublyLinkedList  
- ptrFirst : DLNode<TYPE>*
- ptrLast : DLNode<TYPE>*
- itemCount : unsigned int
+ DLinkedList()  
+ ~DLinkedList()  
   
+ PushFront( newData: TYPE ) : void
+ PopFront() : void
+ GetFront() : TYPE&
   
+ PushBack( newData: TYPE ) : void
+ PopBack() : void
+ GetBack() : TYPE&
   
+ PushAt( newData: TYPE, index: unsigned int ) : void
+ PopAt( index: unsigned int ) : void
+ GetAt( index: unsigned int ) : TYPE&
   
+ IsEmpty() : bool
+ Size() : unsigned int
+ Clear() : void
  • The Push functions are to add new items. There are three varieties: Add to the start of the list (PushFront), Add to the end of the list (PushBack), and Add to somewhere in the middle of the list (PushAtIndex).
  • The Pop functions are to remove items.
  • The Get functions are to access data stored in Nodes.
  • Depending on the design of the List, sometimes the "AtIndex" functions won't be implemented.
template <typename T>
class DLinkedList
{
public:
    DLinkedList();
    ~DLinkedList();

    void PushFront( T newData );
    void PopFront();
    T& GetFront();

    void PushBack( T newData );
    void PopBack();
    T& GetBack();

    void PushAt( T newData, unsigned int index );
    void PopAt( unsigned int index );
    T& GetAt( unsigned int index );

    bool IsEmpty() const;
    unsigned int Size() const;
    void Clear();

private:
    DLNode<T>* ptrFirst;
    DLNode<T>* ptrLast;
    unsigned int itemCount;

    friend class DLinkedListTester;
};

template <typename T>
DLinkedList<T>::DLinkedList()
{
}

template <typename T>
DLinkedList<T>::~DLinkedList()
{
}

template <typename T>
void DLinkedList<T>::Clear()
{
}

template <typename T>
bool DLinkedList<T>::IsEmpty() const
{
    return false; // stub
}

template <typename T>
unsigned int DLinkedList<T>::Size() const
{
    return 0; // stub
}

template <typename T>
void DLinkedList<T>::PushFront( T newData )
{
}

template <typename T>
void DLinkedList<T>::PopFront()
{
}

template <typename T>
T&   DLinkedList<T>::GetFront()
{
    throw runtime_error( "not implemented" ); // stub
}

template <typename T>
void DLinkedList<T>::PushBack( T newData )
{
}

template <typename T>
void DLinkedList<T>::PopBack()
{
}

template <typename T>
T&   DLinkedList<T>::GetBack()
{
    throw runtime_error( "not implemented" ); // stub
}

template <typename T>
void DLinkedList<T>::PushAt( T newData, unsigned int index )
{
}

template <typename T>
void DLinkedList<T>::PopAt( unsigned int index )
{
}

template <typename T>
T&   DLinkedList<T>::GetAt( unsigned int index )
{
    throw runtime_error( "not implemented" ); // stub
}

list-juggle.png

We're going to look at the way functions work, assuming we're using doubly-linked Nodes. This is because it's more straightforward, and once you understand how doubly-linked lists work, you can figure out how a singly-linked list works (it just means more traversing).

4.4. DoublyLinkedListTester

We're going to write unit tests here as well to validate our work. Create DLinkedListTester.h and DLinkedListTester.cpp files and add the following to the header file:

#ifndef _DLINKEDLISTTESTER
#define _DLINKEDLISTTESTER

class DLinkedListTester
{
public:
    void Test_Constructor();

    void Test_Clear();
    void Test_IsEmpty();
    void Test_Size();

    void Test_PushFront();
    void Test_PopFront();
    void Test_GetFront();

    void Test_PushBack();
    void Test_PopBack();
    void Test_GetBack();

    void Test_PushAt();
    void Test_PopAt();
    void Test_GetAt();
};
#endif

You can also premake the function definitions in the .cpp file as well:

#include "DLinkedListTester.h"
#include "DLinkedList.h"

#include <iostream>
#include <string>
using namespace std;

void DLinkedListTester::Test_Constructor()
{
}

void DLinkedListTester::Test_Clear()
{
}

void DLinkedListTester::Test_IsEmpty()
{
}

void DLinkedListTester::Test_Size()
{
}

void DLinkedListTester::Test_PushFront()
{
}

void DLinkedListTester::Test_PopFront()
{
}

void DLinkedListTester::Test_GetFront()
{
}

void DLinkedListTester::Test_PushBack()
{
}

void DLinkedListTester::Test_PopBack()
{
}

void DLinkedListTester::Test_GetBack()
{
}

void DLinkedListTester::Test_PushAt()
{
}

void DLinkedListTester::Test_PopAt()
{
}

void DLinkedListTester::Test_GetAt()
{
}

4.5. main

Let's also create our main() function in a main.cpp file:

#include <iostream>
using namespace std;

#include "DLinkedListTester.h"

int main()
{
    DLinkedListTester tester;
    tester.Test_Constructor();
    tester.Test_Clear();
    tester.Test_IsEmpty();
    tester.Test_Size();
    tester.Test_PopFront();
    tester.Test_PushFront();
    tester.Test_GetFront();
    tester.Test_GetAt();
    tester.Test_PushBack();
    tester.Test_PopBack();
    tester.Test_GetBack();
    tester.Test_PushAt();
    tester.Test_PopAt();

    return 0;
}

4.6. DoublyLinkedList::DoublyLinkedList() constructor

When a new LinkedList is created, it is empty - no Nodes. Since we're working with pointers we need to be safe and set those to nullptr as well. We are expecting the constructor to do the following…

Expectations after construction:
(no term)
ptrFirst should be nullptr.
(no term)
ptrLast should be nullptr.
(no term)
itemCount should be 0.

Unit test

First let's implement the unit test in DLinkedListTester.cpp, adding in what our expectations are and checking for failures:

void DLinkedListTester::Test_Constructor()
{
    cout << endl << "TEST SET: Constructor" << endl;
    { // Test 1
        string test_name = "New LinkedList, check ptrFirst, ptrLast, itemCount";

        DLinkedList<int> dlist;

        // Check for fail states
        if ( dlist.ptrFirst != nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst to be nullptr" << endl;
            cout << "  - Actual   ptrFirst: " << dlist.ptrFirst << endl;
        }
        else if ( dlist.ptrLast != nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrLast to be nullptr" << endl;
            cout << "  - Actual   ptrLast: " << dlist.ptrLast << endl;
        }
        else if ( dlist.itemCount != 0 )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected itemCount to be 0" << endl;
            cout << "  - Actual   itemCount: " << dlist.itemCount << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }
}

Since the Linked List constructor doesn't take in any parameters, we really only need this one test.

If we build and run our program now, the test should fail:

g++ *.h *.cpp -o tester.exe
[21:02:46] rachelwil@compute:../LinkedListStructure/$ ./tester.exe

TEST SET: Constructor
 - [FAIL] New LinkedList, check ptrFirst, ptrLast, itemCount
  - Expected ptrFirst to be nullptr
  - Actual   ptrFirst: 0x7fc994b8b9a0

Function implementation

Remember that the function definitions need to go in the same .h file as the class declaration, just underneath it!

template <typename T>
DLinkedList<T>::DLinkedList()
{
    ptrFirst = nullptr;
    ptrLast = nullptr;
    itemCount = 0;
}

Now when you build and run the tests again it should pass!

4.7. DoublyLinkedList::~DoublyLinkedList() Destructor

The destructor should make sure that all memory is freed when the LinkedList is destroyed. I've moved this functionality into the Clear() function, so just make sure to call Clear() within the destructor. We will implement Clear() here in a moment.

template <typename T>
DLinkedList<T>::~DLinkedList()
{
    Clear();
}

4.8. Clear

The Clear function will be responsible to freeing the memory of all the nodes. You can implement this function by writing a while loop that continues looping while there are still items in the list, calling a Pop function until it is finally empty.

Expectations after Clear():
  1. ptrFirst should be nullptr.
  2. ptrLast should be nullptr.
  3. itemCount should be 0.

We won't be able to test whether the Nodes themselves got destroyed, but we can at least make sure these variables get cleaned up. In fact, you can reuse the constructor test for the Clear function, but set up a single node:

DLinkedList<string> dlist;
dlist.itemCount = 1;
dlist.ptrFirst = new DLNode<string>;
dlist.ptrLast = dlist.ptrFirst;

And make sure that the Clear function is called before your if/else if/else fail/pass statements:

dlist.Clear();

Function implementation

While our list is not empty, we want to keep removing things. We can do this with the front or the back of the list.

Take note:

  • Since this function relies on other functions, its functionality won't properly work until these functions are implemented. Additionally, the program won't build until you at least have function stubs for IsEmpty and PopFront.
  • Additionally, until PopFront is implemented, the tests won't run (every time a LinkedList is destroyed, it will get stuck at while ( !IsEmpty() ) because nothing is making it empty!
template <typename T>
void DLinkedList<T>::Clear()
{
    while ( !IsEmpty() )
    {
        PopFront();

    }
  ptrFirst = nullptr;
  ptrLast = nullptr;
}

4.9. IsEmpty

Expectations of IsEmpty():
  1. Returns true if the node count is 0.
  2. Returns false otherwise.

Unit test

I'll start with the first test - an empty list should have IsEmpty() return true. You'll implement the other scenario.

void DLinkedListTester::Test_IsEmpty()
{
    cout << endl << "TEST SET: IsEmpty" << endl;

    { // Test 1
        string test_name = "Create empty list, check IsEmpty result";

        DLinkedList<int> dlist;
        dlist.itemCount = 0;

        bool expect_result = true;
        bool actual_result = dlist.IsEmpty();

        // Check for fail states
        if ( actual_result != expect_result )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected IsEmpty(): " << expect_result << endl;
            cout << "  - Actual   IsEmpty(): " << actual_result << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    // TODO: Add one more test for when list is not empty.
}

Function implementation

You can then implement the function as such:

template <typename T>
bool DLinkedList<T>::IsEmpty() const
{
    return ( itemCount == 0 );
}

4.10. Size

Return the value of itemCount.

Expectations of Size():
  1. Returns the value stored in itemCount.

Unit test

void DLinkedListTester::Test_Size()
{
    cout << endl << "TEST SET: Size" << endl;

    { // Test 1
        string test_name = "Create empty list, check Size result";

        DLinkedList<int> dlist;
        dlist.itemCount = 0;

        unsigned int expect_result = 0;
        unsigned int actual_result = dlist.Size();

        // Check for fail states
        if ( actual_result != expect_result )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected Size(): " << expect_result << endl;
            cout << "  - Actual   Size(): " << actual_result << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    // TODO: Add one more test for when list has a larger itemCount.
}

Function implementation

The implmeentation should be straightforward:

template <typename T>
unsigned int DLinkedList<T>::Size() const
{
    return itemCount;
}

4.11. PopFront

Expectations of PopFront():
  • For an empty list:
    1. Throw an exception
  • For a list with only 1 item:
    1. Delete the only Node.
    2. Set List's ptrFirst and ptrLast to nullptr.
    3. Subtracts 1 from itemCount.
  • For a list with more than 1 item:
    1. Updates List ptrFirst to be the second Node.
    2. Deletes the old-first.
    3. Updates the new-first's ptrPrev to nullptr.
    4. Subtracts 1 from itemCount.

Unit test

Since we have 3 difference scenarios we're looking for, I'm going to implement 3 unit tests here. You can use these for reference later when implementing Test_PopBack() on your own.

void DLinkedListTester::Test_PopFront()
{
    cout << endl << "TEST SET: PopFront" << endl;

    { // Test 1
        string test_name = "Try to pop from empty list - get exception?";

        DLinkedList<int> dlist;
        dlist.itemCount = 0;

        bool exception_thrown = false;

        try
        {
            dlist.PopFront();
        }
        catch( ... ) // Catch all exceptions
        {
            exception_thrown = true;
        }

        // Check for fail states
        if ( exception_thrown == false )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected exception thrown!" << endl;
            cout << "  - Actually no exception thrown :(" << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    { // Test 2
        string test_name = "Try to pop from list with 1 Node.";

        // Setup
        DLinkedList<int> dlist;
        dlist.ptrFirst = new DLNode<int>;
        dlist.ptrLast = dlist.ptrFirst;
        dlist.itemCount = 1;

        // Action
        dlist.PopFront();

        // Check for fail states
        if ( dlist.itemCount != 0 )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected itemCount to be 0" << endl;
            cout << "  - Actual   itemCount: " << dlist.itemCount << endl;
        }
        else if ( dlist.ptrFirst != nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst to be nullptr" << endl;
            cout << "  - Actual   ptrFirst: " << dlist.ptrFirst << endl;
        }
        else if ( dlist.ptrLast != nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrLast to be nullptr" << endl;
            cout << "  - Actual   ptrLast: " << dlist.ptrLast << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    { // Test 3
        string test_name = "Try to pop from list with 3 Nodes.";

        // Setup
        DLinkedList<string> dlist;
        DLNode<string>* nodeA = new DLNode<string>("A");
        DLNode<string>* nodeB = new DLNode<string>("B");
        DLNode<string>* nodeC = new DLNode<string>("C");

        nodeA->ptrNext = nodeB;
        nodeB->ptrPrev = nodeA;
        nodeB->ptrNext = nodeC;
        nodeC->ptrPrev = nodeB;

        dlist.ptrFirst = nodeA;
        dlist.ptrLast = nodeC;
        dlist.itemCount = 3;

        // Action
        dlist.PopFront();

        // Check for fail states
        if ( dlist.itemCount != 2 )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected itemCount to be 2" << endl;
            cout << "  - Actual   itemCount: " << dlist.itemCount << endl;
        }
        else if ( dlist.ptrFirst == nodeA )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst to not be nodeA anymore." << endl;
            cout << "  - Actual   ptrFirst still pointing to nodeA." << endl;
        }
        else if ( dlist.ptrFirst->ptrPrev != nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst->ptrPrev to be nullptr" << endl;
            cout << "  - Actual   ptrFirst->ptrPrev: "
                 << dlist.ptrFirst->ptrPrev << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }
}

Function implementation

template <typename T>
void DLinkedList<T>::PopFront()
{
    if ( IsEmpty() ) // 0 items in list
    {
        throw runtime_error( "Can't pop from empty list!" );
    }

    else if ( Size() == 1 ) // removing last item
    {
        delete ptrFirst;
        ptrFirst = nullptr;
        ptrLast = nullptr;
        itemCount--;
    }

    else
    {
        ptrFirst = ptrFirst->ptrNext; // Set new-first
        delete ptrFirst->ptrPrev;     // Delete old-first
        ptrFirst->ptrPrev = nullptr;  // Reset node's ptrFirst
        itemCount--;
    }
}

Running the tests

Now you should finally be able to build and run the tests. Before, without PopFront implemented, the program would hang during destruction.

g++ *.h *.cpp -o tester.exe && ./tester.exe

TEST SET: Constructor
 - [PASS] New LinkedList, check ptrFirst, ptrLast, itemCount

TEST SET: Clear
 - [PASS] New LinkedList, check ptrFirst, ptrLast, itemCount

TEST SET: IsEmpty
 - [PASS] Create empty list, check IsEmpty result

TEST SET: Size
 - [PASS] Create empty list, check Size result

TEST SET: PopFront
 - [PASS] Try to pop from empty list - get exception?
 - [PASS] Try to pop from list with 1 Node.
 - [PASS] Try to pop from list with 3 Nodes.

4.12. PushFront

Expectations of PushFront( T newData ):
  1. A new Node will be set up, its data will be set to the newData passed in.
  2. If the Linked List is empty, then the new node will become its first and last node.
  3. Otherwise if the list is NOT empty:
    • the new node will become the new-first item
    • old-first's ptrPrev will point to new-first, and
    • new-first's ptrNext will point to old-first.

Unit test

Here I have tests for an empty list and a non-empty list. You again don't need to add any additional tests to this one, but you will use these for reference for Test_PushBack().

void DLinkedListTester::Test_PushFront()
{
    cout << endl << "TEST SET: PushFront" << endl;

    { // Test 1
        string test_name = "Add item to empty list.";

        // Setup
        DLinkedList<string> dlist;
        dlist.itemCount = 0;

        // Action
        dlist.PushFront( "X" );

        // Check for fail states
        if ( dlist.itemCount != 1 )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected itemCount to be 1" << endl;
            cout << "  - Actual   itemCount: " << dlist.itemCount << endl;
        }
        else if ( dlist.ptrFirst == nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst to NOT be nullptr." << endl;
            cout << "  - Actual   ptrFirst is nullptr." << endl;
        }
        else if ( dlist.ptrLast == nullptr )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrLast to NOT be nullptr." << endl;
            cout << "  - Actual   ptrLast is nullptr." << endl;
        }
        else if ( dlist.ptrFirst->data != "X" )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst->data to be \"X\"" << endl;
            cout << "  - Actual   ptrFirst->data: \""
                 << dlist.ptrFirst->data << "\"" << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    { // Test 2
        string test_name = "Add item to non-empty list.";

        // Setup
        DLinkedList<string> dlist;
        DLNode<string>* nodeA = new DLNode<string>("A");
        DLNode<string>* nodeB = new DLNode<string>("B");
        DLNode<string>* nodeC = new DLNode<string>("C");

        nodeA->ptrNext = nodeB;
        nodeB->ptrPrev = nodeA;
        nodeB->ptrNext = nodeC;
        nodeC->ptrPrev = nodeB;

        dlist.ptrFirst = nodeA;
        dlist.ptrLast = nodeC;
        dlist.itemCount = 3;

        // Action
        dlist.PushFront( "X" );

        // Check for fail states
        if ( dlist.itemCount != 4 )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected itemCount to be 4" << endl;
            cout << "  - Actual   itemCount: " << dlist.itemCount << endl;
        }
        else if ( dlist.ptrFirst == nodeA )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst to NOT be nodeA anymore." << endl;
            cout << "  - Actual   ptrFirst is still nodeA." << endl;
        }
        else if ( dlist.ptrFirst->data != "X" )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst->data to be \"X\"" << endl;
            cout << "  - Actual   ptrFirst->data: \""
                 << dlist.ptrFirst->data << "\"" << endl;
        }
        else if ( dlist.ptrFirst->ptrNext != nodeA )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected ptrFirst->ptrNext nodeA" << endl;
            cout << "  - Actual   ptrFirst->ptrNext: "
                 << dlist.ptrFirst->ptrNext << endl;
            cout << endl;
            cout << "  - All nodes:" << endl;
            cout << "   - nodeA: " << nodeA << endl;
            cout << "   - nodeB: " << nodeB << endl;
            cout << "   - nodeC: " << nodeC << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }
}

Function implementation

We will need to check for the two different scenarios: Adding a first item to an empty list, and adding a new front item to a non-empty list.

template <typename T>
void DLinkedList<T>::PushFront( T newData )
{
    if ( IsEmpty() ) // Adding the first item
    {
        ptrFirst = new DLNode<T>( newData );
        ptrLast = ptrFirst;
        itemCount++;
    }

    else // Items already in list
    {
        DLNode<T>* newNode = new DLNode<T>( newData );
        newNode->ptrNext = ptrFirst;
        ptrFirst->ptrPrev = newNode;
        ptrFirst = newNode;
        itemCount++;
    }
}

4.13. GetFront

Expectations of GetFront():
  1. If the list is empty, then throw an exception.
  2. Otherwise return the data stored in the ptrFirst node.

Unit test

The Get function will either throw an exception (if the list is empty), or return the data itself, so I am checking for both:

void DLinkedListTester::Test_GetFront()
{
    cout << endl << "TEST SET: GetFront" << endl;
    { // Test 1
        string test_name = "Try to get from empty list - get exception?";

        DLinkedList<int> dlist;
        dlist.itemCount = 0;

        bool exception_thrown = false;

        try
        {
            int blah = dlist.GetFront();
        }
        catch( ... ) // Catch all exceptions
        {
            exception_thrown = true;
        }

        // Check for fail states
        if ( exception_thrown == false )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected exception thrown!" << endl;
            cout << "  - Actually no exception thrown :(" << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    { // Test 2
        string test_name = "Try to access front item from list with 1 node.";

        // Setup
        DLinkedList<string> dlist;
        dlist.ptrFirst = new DLNode<string>("X");
        dlist.ptrLast = dlist.ptrFirst;
        dlist.itemCount = 1;

        // Action
        string expect_result = "X";
        string actual_result = dlist.GetFront();

        // Check for fail states
        if ( actual_result != expect_result )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected GetFront(): " << expect_result << endl;
            cout << "  - Actual   GetFront(): " << actual_result << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }
}

Function implementation

And the function implementation is pretty simple:

template <typename T>
T&   DLinkedList<T>::GetFront()
{
    if ( IsEmpty() ) // 0 items in list
    {
        throw runtime_error( "Can't get from empty list!" );
    }

    return ptrFirst->data;
}

4.14. GetAt

Expectations of GetAt( unsigned int index ):
  1. If the index is invalid, throws an exception.
  2. Or if the list is empty, throws an exception.
  3. Otherwise return the data at that position.

Unit test

We need to check that two error states are handled here: An empty list, and an invalid index, as well as making sure that if we are accessing a node that we retrieve the data that we expect.

void DLinkedListTester::Test_GetAt()
{
    cout << endl << "TEST SET: GetAt" << endl;
    { // Test 1
        string test_name = "Try to get from empty list - get exception?";

        DLinkedList<int> dlist;
        dlist.itemCount = 0;

        bool exception_thrown = false;

        try
        {
            int blah = dlist.GetAt(1);
        }
        catch( ... ) // Catch all exceptions
        {
            exception_thrown = true;
        }

        // Check for fail states
        if ( exception_thrown == false )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected exception thrown!" << endl;
            cout << "  - Actually no exception thrown :(" << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    { // Test 2
        string test_name = "Try to get from invalid index - get exception?";

        DLinkedList<int> dlist;
        dlist.ptrFirst = new DLNode<int>(123);
        dlist.itemCount = 1;

        bool exception_thrown = false;

        try
        {
            int blah = dlist.GetAt(2);
        }
        catch( ... ) // Catch all exceptions
        {
            exception_thrown = true;
        }

        // Check for fail states
        if ( exception_thrown == false )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected exception thrown!" << endl;
            cout << "  - Actually no exception thrown :(" << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }

    { // Test 3
        string test_name = "Try to access front item from list with 3 nodes.";

        // Setup
        DLinkedList<string> dlist;
        DLNode<string>* nodeA = new DLNode<string>("A");
        DLNode<string>* nodeB = new DLNode<string>("B");
        DLNode<string>* nodeC = new DLNode<string>("C");

        nodeA->ptrNext = nodeB;
        nodeB->ptrPrev = nodeA;
        nodeB->ptrNext = nodeC;
        nodeC->ptrPrev = nodeB;

        dlist.ptrFirst = nodeA;
        dlist.ptrLast = nodeC;
        dlist.itemCount = 3;

        // Action
        string expect_result = "B";
        string actual_result = dlist.GetAt(1);

        // Check for fail states
        if ( actual_result != expect_result )
        {
            cout << " - [FAIL] " << test_name << endl;
            cout << "  - Expected GetAt(1): " << expect_result << endl;
            cout << "  - Actual   GetAt(1): " << actual_result << endl;
        }
        else
        {
            cout << " - [PASS] " << test_name << endl;
        }
    }
}

Function implementation

Again we need our error checks. If there are no errors, we use a pointer to point to the first address in the list. From there, we need to loop index amount of times to get to the proper location. Once we're there we return the data.

template <typename T>
T&   DLinkedList<T>::GetAt( unsigned int index )
{
    if ( IsEmpty() ) // 0 items in list
    {
        throw runtime_error( "Can't get from empty list!" );
    }

    if ( index < 0 || index >= itemCount ) // bad index
    {
        throw runtime_error( "Can't get from invalid index!" );
    }

    DLNode<T>* ptrWalker = ptrFirst;
    for ( unsigned int i = 0; i < index; i++ ) // walk to index
    {
        ptrWalker = ptrWalker->ptrNext;
    }

    return ptrWalker->data; // return the data here
}

4.15. Tips for the remaining functions

These implementations should cover the patterns you need to complete the rest of the structure, as well as the more graphical explanations of implementations from the "List class" section.

Make sure to just tackle one function - and one scenario per function - at a time. Build a test for one thing at a time. Take it step-by-step - it will be easier to debug issues that way.

And don't forget that you can build it with debug symbols in this way:

g++ -g *.cpp -o tester.exe

And run the debugger with:

gdb tester.exe         (LINUX/WINDOWS)

lldb tester.exe        (MAC)

4.16. PopBack

Expectations of PopBack():
  • For an empty list:
    1. Throw an exception
  • For a list with only 1 item:
    1. Delete the only Node.
    2. Set List's ptrFirst and ptrLast to nullptr.
    3. Subtracts 1 from itemCount.
  • For a list with more than 1 item:
    1. Updates List ptrLast to be the second-to-last Node.
    2. Deletes the old-last.
    3. Updates the new-last's ptrNext to nullptr.
    4. Subtracts 1 from itemCount.

4.17. PushBack

Expectations of PushBack( T newData ):
  1. A new Node will be set up, its data will be set to the newData passed in.
  2. If the Linked List is empty, then the new node will become its first and last node.
  3. Otherwise if the list is NOT empty:
    • the new node will become the new-last item
    • old-last's ptrNext will point to new-last, and
    • new-last's ptrPrev will point to old-last.

4.18. GetBack

Expectations of GetBack():
  1. If the list is empty, then throw an exception.
  2. Otherwise return the data stored in the ptrLast node.

4.19. PopAt

Expectations of PopAt( unsigned int index ):
  1. If the index is invalid, throws an exception.
  2. Or if the list is empty, throws an exception.
  3. If index is 0, call PopFront instead.
  4. If index is itemCount-1, call PopBack instead.
  5. Otherwise:
    • A walker will be used to find the location to be deleted.
    • "before" is walker->ptrPrev, "after" is walker->ptrNext.
    • before's ptrNext is after.
    • after's ptrPrev is before.
    • delete the node at the walker.
    • decrement the itemCount.

4.20. PushAt

Expectations of PushAt( T newData, unsigned int index ):
  1. If the index is invalid, throws an exception.
  2. If index is 0, call PushFront instead.
  3. If index is itemCount, call PushBack instead.
  4. Otherwise:
    • A walker will be used to find the location of the current index item.
    • We will create a new node.
    • "before" is walker->ptrPrev, "after" is walker. (NOT ptrNext!)
    • before's ptrNext is new node.
    • new node's ptrPrev is before.
    • new node's ptrNext is after.
    • after's ptrPrev is new node.
    • Increment item count by 1.

Author: RachelWil

Created: 2026-10-16 Fri 20:39

Validate