A linked list is a series of nodes in memory such that:
A linked list is used for the same purposes as an array. However, the linked list has some advantages:
An array is of fixed size (unless it is dynamically allocated), a linked list can grow by grabbing new memory off the heap as needed.
If you store a list in an array and then delete an item in the middle, then you must move a lot of items down one to close up the gap. But in a linked list, you simply reroute the pointers around the node to delete, and then you delete it.
#include <iostream>
#include <string>
using namespace std;
typedef string listType;
//Node class value semantics: No copy constructor,
// system provided = functionality.
//Node class invariant: A node holds a datum and a pointer
// to another node. The intent is to use the node as the
// basic building block for a linked list: a chain of
// nodes.
class node
{
public:
node (listType);
void setData (listType);
void setNext (node*);
listType getData () const;
node* getNext () const;
private:
listType data;
node* next;
};
#include "node.h"
node::node (listType it)
{
//pre-condition: it is the datum to be stored in the node
//post-condition: it gets stored in the node
data = it;
next = NULL;
}
void node::setData (listType it)
{
//pre-condition: it is the datum to be stored in the node
//post-condition: it gets stored in the node
data = it;
}
void node::setNext (node* aNode)
{
//pre-condition: aNode is the address of any existing node
//post-condition: this node points to aNode
next = aNode;
}
listType node::getData () const
{
return data;
}
node* node::getNext () const
{
//Returns the address of the node that this node points to.
return next;
}
#include "node.h"
//linked class value semantics: copy constructor and
// = work.
//linked class invariant: The class represents a linked
// list, which is a chain of nodes. Each node holds
// data, and each node except the last points to the next
// node. The last node points to NULL.
class linked
{
public:
linked ();
linked (linked&);
linked (listType [], int);
~linked ();
int getSize ();
void addOnEnd (listType);
void insertBefore (int, listType);
void deleteLink (int);
void setDataInLink (int, listType);
listType getNthData (int);
private:
//head is the address of the first node in the list.
//tail is the address of the last node in the list. Tail makes it
// easier and faster to add nodes.
node* head;
node* tail;
int size;
//Utility functions: used only by the Linked class:
void deleteAll ();
node* getNthAddress (int);
void deleteWithOneNode ();
void deleteAtBeginning ();
void deleteLast ();
void deleteInMiddle (int);
};
#include "linked.h"
linked::linked () //Default constructor
{
size = 0;
head = tail = NULL;
}
linked::linked (linked& it) //Copy constructor
{
//Copy over the size.
size = it.size;
head = NULL;
//Copy over the nodes, if there are nodes. Daisy chain the pointers.
// head is the address of the first node, and tail is
// the address of the last.
if (size > 0)
{
head = new node (it.head -> getData ());
node *theNode = head, *newNode;
for (int n = 1; n < size; n++)
{
newNode = new node (it.getNthData (n));
theNode->setNext (newNode);
theNode = newNode;
}
tail = theNode;
}
}
linked::linked (listType aList [], int howMany)
{
//Note the length of the array.
size = howMany;
//Make a node out of the first item in the array.
head = new node (aList [0]);
//Make this node the head.
node *theNode = head;
node *newNode;
//Make a new node for each of the remaining items in the array
// and daisy chain the pointers.
for (int n = 1; n < size; n++)
{
newNode = new node (aList [n]);
theNode->setNext (newNode);
theNode = newNode;
}
//The tail is the address of the last node.
tail = theNode;
}
linked::~linked ()
{
deleteAll ();
}
int linked::getSize ()
{
return size;
}
void linked::deleteAll ()
{
//post-condition: All nodes in the list are deleted.
node* temp;
while (head != NULL)
{
temp = head;
head = head->getNext ();
delete temp;
}
head = tail = NULL;
size = 0;
}
node* linked::getNthAddress (int n)
{
//Pre-condition: n should be 0 or more and less than size.
//Post-condition: the address of the nth node is returned.
node *theNode = NULL;
if (n >= 0 && n < size)
{
int place = 0; //Index of current node
theNode = head; //Address of the current node
//Find the address of the nth node
while (place < n)
{
theNode = theNode->getNext ();
place++;
}
}
return theNode;
}
listType linked::getNthData (int n)
{
//Pre-condition: n should be 0 or more and less than size.
//Post-condition: returns the data in the nth node.
return getNthAddress (n) -> getData ();
}
void linked::addOnEnd (listType it)
{
//Pre-condition: it is a piece of data to be appended on the end
// of the list.
//Post-condition: The result is a new node on the end of the list
// containing it as data, and a new tail.
node* newOne = new node (it);
if (size == 0)
{
head = newOne;
tail = newOne;
}
else
{
tail->setNext (newOne);
tail = newOne;
}
size++;
}
void linked::insertBefore (int n, listType it)
{
//Pre-condition: n is the index of the node before which we want to
// insert a new node containing data it. n should be 0 or more and less
// than size.
//Post-condition: A new node containing it is inserted before the old node n.
//If the list is empty, need only create a new node and point the head
// and tail to it.
if (n == 0 && size == 0)
{
head = new node (it);
tail = head;
size++;
}
//If we insert before the beginning, then make a new node, set it to point
// to the head, then revise the head.
else if (n == 0 && size > 0)
{
node* newOne = new node (it);
newOne->setNext (head);
head = newOne;
size++;
}
//If we insert anywhere else, then make a new node, make the previous node
// point to it, and make the new node point to the node before which we
// inserted.
else if (n < size)
{
int place = 0;
node *theNode = getNthAddress (n);
node *prev = getNthAddress (n - 1);
node* newOne = new node (it);
prev ->setNext (newOne);
newOne->setNext (theNode);
size++;
}
}
void linked::deleteLink (int n)
{
//Pre-condition: n is the index of the node to be deleted. n should be
// 0 or more and less than size.
//Post-condition: the nth node has been deleted.
if (size == 1 && n == 0)
{
deleteWithOneNode ();
}
else if (size > 1 && n == 0)
{
deleteAtBeginning ();
}
else if (n > 0 && n < size - 1 && size > 1)
{
deleteInMiddle (n);
}
//Finally handle the case of deleting the last one.
else if (size > 1 && n == size - 1)
{
deleteLast ();
}
}
void linked::deleteWithOneNode ()
{
//Post-condition: The only node is deleted.
//If there is only one node then just delete this node.
delete head;
head = NULL;
size = 0;
}
void linked::deleteAtBeginning ()
{
//Post-condition: the first node in the list is deleted.
//If there are many nodes and we are deleting at the beginning, then
// set the head to the next node after the head and delete the old
// head node.
node* temp = head;
head = head -> getNext ();
delete temp;
size--;
}
void linked::deleteLast ()
{
//postcondition: last node in the list is deleted.
node* newTail = getNthAddress (size - 2);
delete tail;
tail = newTail;
tail -> setNext (NULL);
size--;
}
void linked::deleteInMiddle (int n)
{
//Pre-condition: n is 0 or more and less than size.
//Post-condition: the nth node is deleted.
//If we are deleting somewhere in the middle, then reroute the pointers
// around the node to be deleted, then delete that node.
//Find the addresses of the n-1 st and n th nodes.
node *theNode = getNthAddress (n);
node *prev = getNthAddress (n - 1);
//Reroute the pointers around the node to be deleted.
prev -> setNext (theNode -> getNext ());
//And delete the node.
delete theNode;
size--;
}
void linked::setDataInLink (int n, listType newOne)
{
//Pre-condition: n is the index of the node whose data is to be changed.
// newOne is the new data. n should be 0 or more and less than size.
//Post-condition: the data in the nth node has been changed to newOne.
if (n >= 0 && n < size)
{
node *location = getNthAddress (n);
location->setData (newOne);
}
}