In this post i am going to show you how to implement a simple Linked List data structure in C++ using Visual Studio 2008. However, you can use your favorite IDE to build this example. You can also check the original post at my blog where complete source code of this post is available.
In simplistic view Linked List is a collection of individual List Nodes interconnected with each Node pointing to the Node ahead of it. So to get us started, we need List Nodes first and then we’ll build Linked List data structure using those.
Fire up your favorite IDE and create a new project and add a header file named Node.h. This header file contains the interface of the Node class. Following is the code for this header file.
1: #pragma once
2:
3: class Node
4: {
5: public:
6: Node(void);
7: ~Node(void);
8:
9: int get();
10: void set(int object);
11:
12: Node * getNext();
13: void setNext(Node * nextNode);
14:
15: private:
16: int object;
17: Node * nextNode;
18: };
In the code snippet above, first data member is an integer type that will hold the node value and the second data member is a pointer to the next node in the list (Null if this is the last node in the list). Getter and Setter methods for the data members are also defined.
Now create a new class and name it Node.cpp. This will implement the interface defined in the Node.h header file. Following is the code for the Node.cpp.
1: #include "Node.h"
2:
3: Node::Node(void){
4: }
5:
6: Node::~Node(void){
7: }
8: int Node::get() {
9: return object;
10: }
11:
12: void Node::set(int object) {
13: this->object = object;
14: }
15:
16: Node * Node::getNext() {
17: return nextNode;
18: }
19:
20: void Node::setNext(Node * nextNode) {
21: this->nextNode = nextNode;
22: }
To create a linked list of Nodes we have to create a List class. For that create a new header file named List.h and copy the following code snippet into it. Include the Node.h header file created earlier.
1: #pragma once
2: #include "Node.h"
3: class List
4: {
5: public:
6: List(void);
7: ~List(void);
8: void add (int addObject);
9: int get();
10: bool next();
11: friend void traverse(List list);
12: friend List addNodes();
13: void start();
14: void remove();
15: int length();
16:
17: private:
18: int size;
19: Node * headNode;
20: Node * currentNode;
21: Node * lastCurrentNode;
22: };
In this code snippet there is one data member named size. It will hold the current size of the linked list. A part from that three Node pointer are declared pointing to the Head Node, Current Node and the Last Current Node as their names suggest. Two friend functions are declared namely traverse() and addnodes().In the second part I'll show you the implementation of the List class and i'll finish with testing the Linked List in main method