/*

Linked Lists

What is a linked list? Before we answer that question, let me ask a

different question. Suppose you had a program that kept track of the

names of employees. How would you store these names? One way would

be to use an array. You can use something like NameStruct Employees[50],

where NameStruct was a structure with a first and last name. But what

happens when you have more than 50 employees? What if you have 100?

Or what about 1000? What if you won't ever really know? 

You can prepare for the worst case, and create a huge array of say 10,000

arrays. But what really is the worst case? And more importantly, when

there are only a few employees, you would be wasting a lot of precious

memory allocating a bunch of empty NameStruct variables.

A nice solution to this problem, is a flexible linked list. A linked

list is a data structure, which can grow and shrink as you want it to.

You can add items to it, you can access the items on it, and you can

delete items from it. And the whole time, you only allocate an amount

of memory proportional to the number of items you have.

So how does a linked list accomplish this task?

A linked list takes advantage of the fact that you can store memory

addresses to other variables. We have structures (sometimes called nodes)

which contain the information you want. Along with that information,

is the address to another structure (node). 

Let A, B, and C be NameStruct (nodes). Let X --> Y represent

the fact that X contains the memory address of Y (the so-called "link").

A --> B --> C --> Null

is a linked list with three nodes, terminated with a Null node.

How do we access the elements? Say we know the address of A, but we

are looking for the last name associated with someone who has the 

first name "George" (say, C.firstName). We can check what address

A is storing, and find out it's B. And B.firstName isn't "George".

So, we move on, and check what address B is storing, and find out 

it's C. And C.firstName is "George" so we have a winner.

In this manner, we can access any element in the list, just by knowing

the first node's address. But this isn't the power of the linked list.

The best part about the linked list is that you can add and remove

elements, while only using the amount of memory you need. It requires

some dynamic allocation (which C++ provides with new/delete). However,

if it's implemented well, most of the details can be hidden nicely.

using a linked list should be easy as pie. 

On the other hand, implementing a linked list can be tedious,

depending on how many features you would like it to have. for example,

when you add elements, should it be in sorted order?

Since this is just a simple description of a linked list, there are

no fancy features.

So let's go through the code together. 

*/

#include 

/* Here is our Node (our structure) that contains the information

we want along with a memory address to the next Node on the list.

When the list is empty, our there is no next. In fact, there is

no Node at all, as you will see in a moment. 

*/

class Node

    {

    public:

    int x; /* The information we really want to store. */

    Node *next;/* The address to the next Node in the list. */

    Node() { next = NULL; } /* Start of with no next Node. */

    /* Here, we want to get rid of the next Node before getting rid of

    this one. Why? It's a tricky way to get rid of all the nodes, by

    simply getting rid of the first once. Think "chain-reaction". 

    */

     ~Node() { if (next != NULL) delete next; } 

};

/* Here is our List, which manages all the Nodes. using the List

interface, we can add nodes, remove nodes, or print out the nodes

that are in the list. 

*/

class List

    {

    /* The "head" is a variable that points to the first node in our

    list. Keep in mind, "head" isn't a Node itself. It's just the

    memory address of the first actual node. In the beginning, when

    there are no items in our list, "head" doesn't have an address

    and that means head = NULL.

    */

    Node *head;

    /* The "tail" is similar to the "head" except it has the memory

    address of the last actual node. It's not a necessary variable,

    but it's handy for adding elements because we don't have to 

    go through the entire chain to find the last element in our

    list. 

    */

    Node *tail;

    /* The size of the list will be the number of elements in it. It's 

    not really necessary, just something that might come in handy.

    */

    int size;

    public:

    List() { size = 0; head = NULL; tail = NULL; }

    /* Deleting the head removes ALL the links in the linked list. Why?

    Think "chain-reaction". The head doesn't disappear until head's

    "next" variable disappears, which doesn't disappear until it's own

    "next" variable disappears, and so on...

    */

    ~List() { delete head; }

    /* Some typical linked list functions */

    void add(int x);

    void del(int x);

    void print();

};

/* How do we add an element to a linked list? We create a new Node using

new Node (hmm, C++ syntax makes sense I guess). We give it the data

we want (in this case, just a number). Then, we make the tail's "next"

variable (which is the last element on the list) be the temp Node. 

We have to take care of the special case when this is the first node

on the list, otherwise "head" won't be have any "next" address (that is,

"head" won't be pointing to anything).

*/

void List::add(int x)

    {

    Node *temp;

    temp = new Node;

    temp->x = x;

        if (size == 0) {

        head = temp;

        tail = temp;

        } else {

        tail->next = temp;

        tail = temp;

    }

    /* Our list is now one size bigger. */

    size++; 

    cout << "List::add(" << temp->x << ")." << endl;

}

/* How do we delete an element from a linked list? Well, for this

procedure, think "heart bypass surgery". We have a chain of Nodes

like this:

A --> B --> C --> D --> E --> Null

and to delete C, we would simply have B point to D. So we have 

A --> B C --> D --> E --> Null

||

\-----------/

and C is no longer part of the chain. Still, we should get rid of

the memory allocated for C, and we do that using the delete 

keyword in C++.

Note: Before we can delete C, we need to let C's "next" variable

be NULL. Why? Remember, C won't disappear until C's "next" also

disappears, and so on, and we'll end up getting rid of D and E as

well. That's not what we want. 

A --> B --------> D --> E --> Null

*/

void List::del(int x) { 

Node *temp = head, *prev = head; 

for (int i=0; i

    {

        if (temp->x == x) {

        prev->next = temp->next; 

        if (head == temp)

        head = temp->next;

        temp->next = NULL; 

        delete temp;

        i = size;

    } 

    else { 

    prev = temp; 

    temp = temp->next; 

} 

}

size--; 

cout << "List::del(" << x << ")." << endl;

}

/* How do we print out all of the elements in the list? 

One way to do it, is with a single loop. Use a temporary

variable, which is reassigned to have the value which it's own

"next" variable has, during each loop.

Run the program to see what the output looks like. 

*/

void List::print()

{

Node *temp;

temp = head; 

cout << "List::print() output: ";

do {

cout << "[" << temp->x << "] --> ";

temp = temp->next; 

} while (temp != NULL);

cout << "NULL" << endl;

}

/* And here is the great main function. We just do a few simple

operations on the list, to try out the creation. It's nothing

really special. Then again, I've always thought that the

most precious things in life are the simple things in life.

*/

int main(void)

{

List list;

list.add(1);

list.add(2);

list.add(3);

list.print();

list.del(3);

list.print();

cout << "Done, press enter." << endl;

char c;

cin >> c;

return 0;

}