Simple Linked List | Chinese Rule of Eight

A simple linked list in C++
Basic features
Running time

Features

– add by appending
– search
– remove
– display

A linked list is a bunch of nodes ‘linked’ together by pointers. Each node has a ‘next’ pointer that points tot he next node. This is what creates the link.

First step is to create the node. The node has data and a next pointer. The next pointer should be of the same type this node because after all, the nodes are of the same type.

You’d want to have 2 constructors for the Node. An default empty one, and another where you can assign new values.

Node.h

class Node {

public:

int iData; //data

double priority;

Node * pNext; //pointer to next link

Node() {

iData = -1;

priority = -1;

pNext = nullptr;

}

Node(int data, double priority, Node * next) {

iData = data;

priority = priority;

pNext = next;

}

void displayLink() {

printf( "{ %d , %f }", iData, priority);

}

};

Node.cpp

1	#include "Node.hpp"

LinkedList.hpp

#include <stdio.h>

#include "Node.hpp"

class LinkedList {

private:

Node * head;

public:

//constructor

LinkedList() {

printf("\n --- LinkedList Constructor --- \n");

head = NULL;

}

~LinkedList()

{

printf("\n --- LinkedList Destructor --- \n");

Node * pCurrent = head;

while(pCurrent != NULL)

{

Node * toDelete = pCurrent; //the element we gon delete

pCurrent = pCurrent->pNext; //move!

delete toDelete; //delete it!

}

void append(int data, double priority);

void pop(); //O(1)

Node * find(int data); //O(n)

bool remove(int data); //O(n)

bool isEmpty(); //O(1)

void displayList(); //O(n)

};

Append

1) We have head point to NULL in the beginning

2) First item is initialized through being supplied with values from its constructor parameters. These parameters are int data, double priority, and whatever head is pointing to.

3) In the case of appending the first node, our first node’s pNext should be to what head is pointing to, which is NULL

4) our head then re-points to the newly created Node object. Our first object as been appended.

In programming, we always execute the inner most first. Then we work our way out.

1	head = new Node(data, priority, head);

The inner most is the data parameters.

First, we evaluate data to be a int. We evaluate priority to be a double. Finally, we evaluate head to point to NULL.

Then we pass these 3 values into the constructor of Node. Node object gets created with its attributes initialized. The values are initialized to , and the pNext pointer points to what head is.

Finally, when the Node object has been created, we have our head point to this Node object.

Remove

temp means the temporary node we’re on. Trailer means the pointer behind temp, so that when we remove, we can use the trailer to connect the link.

The important to notice here is

1) evaluating the first item. When temp and trailer are pointing to the same node, we’re at the first node. When we see a match, we remove the node and repoint head to the next node.

2) Moving forward to evaluate the next item involves simply checking to see if we have a match or not. If there NO match we move forward by first, pointing trailer to temp. Then have temp point to temp->next. That way, when temp has a match, then the trailer can link (the node before and after the deleted node) together.

1 2	trailer->pNext = temp->pNext; delete temp; temp = nullptr;

Running Time

Search O(n)
Delete O(n)
Append O(1)

Finding or deleting a specified item requires searching through, on the average, half the items in the list. This requires O(N) comparisons.

An array is also O(N) for these operations, but the linked list is nevertheless faster because nothing needs to be shifted when an item is inserted or removed.

The increased efficiency can be significant, especially if a copy takes much longer than a comparison.

Of course, another important advantage of linked lists over arrays is that the linked list uses exactly as much memory as it needs, and can expand to fill all available memory. The size of an array is fixed when it’s created; this usually leads to inefficiency because the array is too large, or to running out of room because the array is too small.

Vectors, which are expandable arrays, might solve this problem to some extent, but they usually expand in fixed-sized increments (such as doubling the size of the array whenever it’s about to overflow). This use of memory is still not as efficient as a linked list.