A linked list in which each node only has a pointer for the next node, as opposed to having pointers for the next and previous nodes. Most basic singly linked list node:
struct node
{
struct node* next;
//.. some data here
}
In C, singly linked lists are most often implemented by using several functions for adding and deleting nodes attached to a list head, the first node in the list. In C++, classes are often taken advantage off to create list classes with member functions for handling the list. A templated linked list example is below.
#include <iostream>
template<class T> class LinkedList;
template<class T>
class Node
{
T nodedata;
Node(T& data);
Node *next;
friend class LinkedList<T>;
};
template<class T>
Node<T>::Node(T& data)
{
nodedata = data;
next = 0;
}
template<class T>
class LinkedList
{
Node<T>* head;
public:
LinkedList();
~LinkedList();
Node<T>* ReturnHead() { return head; }
Node<T>* SeekElement(int n) { return (*this)[n]; }
T& operator[](int n);
void AddElement(T& data);
void RemoveElement(T* element) { delete element; }
void DeleteList();
};
template<class T>
LinkedList<T>::LinkedList()
{
head = 0;
cout << "Constructed." << endl;
}
template<class T>
LinkedList<T>::~LinkedList()
{
DeleteList();
cout << "Destructed." << endl;
}
template<class T>
T& LinkedList<T>::operator[](int n)
{
Node<T>* temp = head;
for(int i = 0 && temp; i < n && temp; ++i)
temp = temp->next;
return temp->nodedata;
}
template<class T>
void LinkedList<T>::AddElement(T& data)
{
Node<T>* temp = new Node<T>(data);
if(head == 0)
head = temp;
else
{
temp->next = head->next;
head->next = temp;
}
cout << "Element added." << endl;
}
template<class T>
void LinkedList<T>::DeleteList()
{
Node<T>* temp = head;
Node<T>* temp2 = head;
while(temp)
{
temp2 = temp->next;
delete temp;
temp = temp2;
}
cout << "Deleted." << endl;
}
int main()
{
LinkedList<int> list;
int x = 5;
list.AddElement(x);
list.AddElement(x);
list.AddElement(x);
cout << list[1] << endl;
return 0;
}