Linked Lists
(Up to Basic Computer Science : Lists and Arrays)

Linked lists are a special type of list that can be dynamically changed in size. Dynamic structures can be changed depending on the situation as the program runs, while static structures are set in stone as the program compiles.

Linked lists are unique in that they allow the programmer to insert or delete any element in the list quickly and efficiently.

The structure of the linked list is compose of nodes, or sub-units, which stand for the elements of the list. These nodes are interconnected, and thus allow the insertion of new nodes easily; you only need to create the node and connect it to the chain.

So, here is a diagram of a simple linked list:

Thus, the arrows represent the links between the nodes, and each circle (a node) contains data for one element. Notice that the last node's link is pointed to a NULL. This NULL signifies the end of the list.

Here is the code structure for the linked list:

class linked_list {
  public:
    linked_list(void);     // Constructor
    ~linked_list(void);    // Destructor

    void print(void);      // Prints Entire List
    void insert(int item); // Insert Function
    void remove(int item); // Remove Function
    bool search(int item); // Search Function
  
  private:
    linkedNode *first;     // Pointer to first node
};

class linkedNode {
  public:
    int data;            // Data held by this node
    linkedNode *next;    // Pointer to next node
};

This structure needs some explaining. The variable first is a pointer. A pointer is a C++ variable that can be used to modify the values of other variables. If you do not understand pointers, I suggest you consult a book on C++ or take a look at the Cprogramming.com tutorial on pointers.

The search() function just searches the list to see if the value in item exists in the list. The function returns true if the value was found, and false otherwise. The remove() function just goes through the linked list and looks for the value given in item. If it finds this value, the function removes the node containing it and then stops.

The insert() function depends on whether the linked list is ordered or not. If the linked list is not order, insert() just puts the new value at the beginning of the list. If the list is ordered, however, then insert() must first find the location for the new node, and then insert the node in that location.

When the list is first initialized, the value of first would be NULL, because the list is empty (i.e. there are no nodes). When the list is not empty, the last node would have their next link point to NULL.

Take a look at this example here. Here is a linked list:

first -> 2 -> 5 -> 8 -> 9 -> NULL

Let us say we wish to insert the value 3. If the list is unordered, then the value would be inserted at the beginning, and the list would now look as such (note that the value of first would be changed):

first -> 3 -> 2 -> 5 -> 8 -> 9 -> NULL

(Note: the altered links and the inserted value are highlighted in red.) If the list were to be ordered, however, then the new value would be inserted in the middle of the list:

first -> 2 -> 3 -> 5 -> 8 -> 9 -> NULL

Try programming the functions as an exercise. It really isn't as hard as it may seem.