A linked list is a data structure.
A data structure is basically a container of data, which respects certain rules for storing and accessing the data.
In the case of a linked list, data is stored inside nodes.
The nodes are linked to one another, and thus they form the linked list.
One easy way to code a linked list is by defining two classes: Node
A node contains the data and the link (or links) to the other node (or nodes).
If any node has just one link, to the next node in the list, then your list is a "singly-linked list".
If any node has two links, to the previous and next nodes in the list, then your list is a "doubly-linked list".
For simplicity, Node
can be a struct
instead of class
, and because it is only used within the LinkedList
class, it can be defined internally.
A simple beginning could be as shown below. It will get more complicated as you add the missing parts: constructor and destructor for LinkedList
, and functions that make the LinkedList
usable, such as search()
. and insert()
Node *first_node; // first node in the list