Back to Code List
c++

Simple Linked List

This is a simple one-way linked list with insert, remove, and clone list functions.

   LinkedList.h

#include <memory>

struct Node
{
	int data;
	template<class T>
	Node(T v, std::shared_ptr<Node> n)
		:next(n)
		,data(v)
	{}
	std::shared_ptr<Node> next;
};

template<class T>
class LinkedList
{
private:
	std::shared_ptr<Node> head; // variable to contain head node

	std::shared_ptr<Node> clone(std::shared_ptr<Node> n)
	{
	  // will copy a linked list entirely with recursion O(n)
	  if (!n) return nullptr;
	  return std::make_shared<Node>(n->data, clone(n->next));
	};

	void insert(T value, std::shared_ptr<Node>& p)
    {
        if(!head)
		{
			head = std::make_shared<Node>(value,nullptr);
			return;
		}
		
		if(p)
		{
			if (p->data > value)
			{
				auto temp = head;
				head = std::make_shared<Node>(value,temp);
			}
			else if (!(p->next) || p->next->data > value) {
				p->next = std::make_shared<Node>(value,p->next);
				return;
			} else
				insert(value, p->next);
		}
    };

	void remove(T value, std::shared_ptr<Node>& n)
	{
		if (!n) return;
		if (head->data == value)
		{
			head = head->next;
		}
		if (n->data == value)
		{
			if (n->next)
				n = n->next;
			else
				n=nullptr;
		}
		else
			remove(value,n->next); // recurse into next item in list
	};
public:
    LinkedList() :head(0) {};	// constructor
    LinkedList(LinkedList const& other) :head(clone(other.head)) {};	// copy constructor
	~LinkedList() { if (head) head = nullptr; };	// destructor

	void insert(T value) { insert(value, head); };	// initializer of insert recursive loop
	void remove(T value) { remove(value, head); };	// initializer of remove recursive loop

	std::shared_ptr<Node> getHead() { return head; } // returns head node pointer

	template<class X>
	void for_each(std::shared_ptr<Node> startPos, X & n)
	{
		if (startPos) {
			n(startPos->data);
			for_each(startPos->next, n);
		}
	};
};    

   Main.cpp

#include "LinkedList.h"
#include <iostream>
#include <array>

template<class T>
void printList (LinkedList<T> L)
{
	L.for_each(L.getHead(),[](T n) {
        std::cout << n << " ";
    });
	std::cout << std::endl;
};

int main() {
	std::cout << "Inserting set of numbers into LinkedList (L1) and print." << std::endl;
	LinkedList<int> l1;
	std::array<int, 8> data = {2, 3, 6, 9, 15, 20, 28, 42};
	for (int i=0; i<8; ++i) {
		l1.insert(data[i]); 
	}
	std::cout << "before: " << std::endl;
	std::cout << "after:  ";
	printList(l1);

	std::cout << std::endl << std::endl;
	std::cout << "Let's try a linked list of characters. (L2)." << std::endl;
	LinkedList<char> l2;
	std::array<char, 8> data2 = {'b', 'e', 'f', 'p', 'q', 't', 'y', 'z'};
	for (int i=0; i<8; ++i) {
		l2.insert(data2[i]); 
	}
	std::cout << "before: " << std::endl;
	std::cout << "after:  ";
	printList(l2);

	std::cout << std::endl << std::endl;
	std::cout << "Let's copy a linked list and print the values. (L1 -> L3)" << std::endl;
	LinkedList<int> l3(l1);
	std::cout << "before (L1): ";
	printList(l1);
	std::cout << "after  (L3): ";
	printList(l3);

	std::cout << std::endl << std::endl;
	std::cout << "Let's insert some values." << std::endl;
	std::cout << "One at the start of the list (L1) -- the number '1'." << std::endl;
	std::cout << "before: ";
	printList(l1);
	std::cout << "after:  ";
	l1.insert(1);
	printList(l1);

	std::cout << std::endl;
	std::cout << "One at the end of the list (L3) -- the number '87'." << std::endl;
	std::cout << "before: ";
	printList(l3);
	std::cout << "after:  ";
	l3.insert(87);
	printList(l3);

	std::cout << std::endl;
	std::cout << "One somewhere in the middle of the list (L2) -- the character 'i'." << std::endl;
	std::cout << "before: ";
	printList(l2);
	std::cout << "after:  ";
	l2.insert('i');
	printList(l2);

	std::cout << std::endl << std::endl;
	std::cout << "Let's remove the values we just inserted." << std::endl;
	std::cout << "One at the start of the list (L1) -- the number '1'." << std::endl;
	std::cout << "before: ";
	printList(l1);
	std::cout << "after:  ";
	l1.remove(1);
	printList(l1);

	std::cout << std::endl;
	std::cout << "One at the end of the list (L3) -- the number '87'." << std::endl;
	std::cout << "before: ";
	printList(l3);
	std::cout << "after:  ";
	l3.remove(87);
	printList(l3);

	std::cout << std::endl;
	std::cout << "One somewhere in the middle of the list (L2) -- the character 'i'." << std::endl;
	std::cout << "before: ";
	printList(l2);
	std::cout << "after:  ";
	l2.remove('i');
	printList(l2);



	std::cout << std::endl << std::endl;
	return 0;
}