Implementing a Singly Linked List in C++

 

Implementing a Python linked list left me a bit unsatisfied. Does this data structure really qualify as a linked list, or is it some sort of analogue? In searching for an answer, I came across this definition of Linked Lists from Wikipedia:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

While pointers don’t seem to be an explicit requirement, studying a proper linked list in C/C++ seems like a good learning exercise.

Here’s a C++ linked list I came across surfing the web for a simple implementation, annotated piecewise:


#include <iostream>;
using namespace std;

class LinkedList{
struct Node {
int x;
Node *next;</pre>
};

Within the template for a linked list, a structure called node is defined first. Node, representing a single entry in the list, contains two bins, a value and a pointer referencing the next entry.

The Linked List class continues:

public:
LinkedList(){
head = NULL;
}

A value constructor sets the head value to NULL. Any instance of our linked list class starts its life an empty, with the head space set to NULL.

void addValue(int val){
Node *n = new Node();
n->x = val;
n->next = head;
head = n;
}

To this empty list we use a method called addValue to chain items. This method evokes a new instance of the node structure, to which the argument value is passed as the node’s value. Next of this node points to the current head, which for a new linked list function is simply NULL. This new node then is designated as the new head.


int popValue(){
Node *n = head;
int ret = n->x;

head = head->next;
delete n;
return ret;
}

This next method allows us to reverse the effect of the previous prepending addValue function. ret is assigned the value of the current head node’s x. Then, head is reassigned as the current next value. Now that the old next cell is set to the head of the list, it is now safe to delete the previous head node and return its x value.

private:
Node *head;
};

_

Advertisements
Implementing a Singly Linked List in C++

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s