Linked List

A linked list is a data storage technique that allows for variable size container. Linked lists typically consists "connected" nodes containing both data and one or more pointers. The pointer(s) perform the connection to the "next" data item. The most common type of linked lists are single-ended (containing data and one next pointer) and double-ended (containing data and two pointers, next and previous).

The following example illustrates a single ended linked list used to store int data.

Example 5-9 – Linked List

1      // file: ex5-9node.h
2     
3      #ifndef NODE_H
4      #define NODE_H
5     
6      class List;        // forward declaration
7     
8      class Node
9      {
10          int        data_;
11          Node*        next_;
12          Node();            // disable the default ctor
13      public:
14          Node(int d,Node* n) { data_ = d; next_ = n; }
15      friend class List;
16      };
17     
18      #endif

1      // file: ex5-9list.h
2     
3      #ifndef LIST_H
4      #define LIST_H
5     
6      #include "ex5-9node.h"
7     
8      class List
9      {
10          Node*        top_;
11      public:
12          List();
13          ~List();
14          void push(int item);
15          int pop();
16          int top() const;
17          void print() const;
18          bool remove(int item);
19          Node*    find(int item);
20      };
21     
22      #endif

1      // file: ex5-9list.cpp
2     
3      #include <iostream>
4      #include <cstdlib>
5      using namespace std;
6     
7      #include "ex5-9l.h"
8     
9      List::List()
10      {
11          top_ = 0;
12      }
13     
14     
15      List::~List()
16      {
17          Node* temp = top_;
18          while (temp != 0) {
19              top_ = top_ -> next_;
20              delete temp;
21              temp = top_;
22          }
23      }
24      void List::push(int item)
25      {
26          Node* temp = new Node(item,top_);
27          if (!temp) {
28              cerr<<"Unable to allocate memory for a Node. Exiting ...\n";
29              exit(-1);
30          }
31          else {
32              top_ = temp;
33          }
34      }
35     
36     
37      int List::pop()
38      {
39          Node* temp = top_;
40          top_ = top_->next_;
41          int value = temp->data_;
42          delete temp;
43          return value;
44      }
45     
46     
47      int List::top() const
48      {
49          return top_ -> data_;
50      }
51     
52     
53      void List::print() const
54      {
55          Node* temp = top_;
56          while (temp != 0) {
57              cout << temp -> data_ << ' ';
58              temp = temp -> next_;
59          }
60          cout << endl;
61      }
62     
63     
64      Node*    List::find(int item)
65      {
66          Node* temp = top_;
67          while (temp != 0) {
68              if (temp->data_ == item) return temp;
69              temp = temp -> next_;
70          }
71          return 0;
72      }
73     
74     
75      bool List::remove(int item)
76      {
77          if (!find(item)) {
78              cerr << item << " is not in the List\n";
79              return false;
80          }
81          Node* temp1 = top_;
82          Node* temp2;
83          if (top_->data_ == item) {
84              top_ = top_ -> next_;
85              delete temp1;
86              return true;
87          }
88          while (temp1->next_->data_ != item) {
89              temp2 = temp1;
90              temp1 = temp1 -> next_;
91          }
92          temp2 = temp1 -> next_;
93          temp1->next_ = temp2 -> next_;
94          delete temp2;
95          return true;
96      }

1      // file: ex5-9main.cpp
2     
3      #include <iostream>
4      using namespace std;
5     
6      #include "ex5-9list.h"
7     
8      int main (void)
9      {
10          List L;
11          L.push(2);
12          L.push(4);
13          L.push(6);
14          L.push(8);
15          L.push(10);
16          L.print();
17          cout << "top=" << L.top() << endl;
18          if (L.find(2)) cout << 2 << " is in the list\n";
19          if (L.find(5)) cout << 5 << " is in the list\n";
20          if (L.find(6)) cout << 6 << " is in the list\n";
21          if (L.find(10)) cout << 10 << " is in the list\n";
22          L.remove(3);
23          L.remove(6);
24          L.print();
25          L.remove(2);
26          L.remove(10);
27          L.print();
28     
29          return 0;
30      }

****** Output ******

10 8 6 4 2
top=10
2 is in the list
6 is in the list
10 is in the list
3 is not in the List
10 8 4 2
8 4

Example 5-10 – Standard Template Library Solution for Example 5-9

1      // File ex5-10.cpp – STL linked list example
2    
3      #include <iostream>
4      #include <list>
5      #include <algorithm>        // for copy and find algorithms
6      #include <iterator>            // for ostream_iterator
7      using namespace std;
8    
9      void print(list<int>& lint)
10      {
11          copy(lint.begin(),lint.end(),ostream_iterator<int>(cout," "));
12          cout << endl;
13      }
14    
15      bool find(list<int>& lint, int value)
16      {
17          return find(lint.begin(),lint.end(),value)!=lint.end();
18      }
19    
20      int main (void)
21      {
22          list<int> L;
23          L.push_front(2);
24          L.push_front(4);
25          L.push_front(6);
26          L.push_front(8);
27          L.push_front(10);
28          print(L);
29          cout << "top=" << *L.begin() << endl;
30    
31          if (find(L,2)) cout << 2 << " is in the list\n";
32          if (find(L,5)) cout << 5 << " is in the list\n";
33          if (find(L,6)) cout << 6 << " is in the list\n";
34          if (find(L,10)) cout << 10 << " is in the list\n";
35          L.remove(3);
36          L.remove(6);
37          print(L);
38          L.remove(2);
39          L.remove(10);
40          print(L);
41          return 0;
42      }

******  Output  ******

10 8 6 4 2
top=10
2 is in the list
6 is in the list
10 is in the list
10 8 4 2
8 4