Linked Lists 101

Hello..

I have studied.. and studied and studied the concepts of linked lists for several weeks now.. I think I have hit the wall in my c++ career.. I understand all the theory behind them.. but when it comes to coding one up.. I am stuck.. I think the reason for this is two fold:

1.) My book I have used thus far do not provide an fully written program as an example of how to use linked lists. (but does provide full code for other things such as "stacks" and "queues"). It provides some example classes.. so there is some ambiguity when it comes to actually coding one up.

2.) Linked lists are more abstract in nature.. as compared to other data structures... like the array for example, which is much more easy to manipulate.. and doesn't require a bunch of user defined functions.

I have very seldom made a plea for help.. but this is it.

I have provided a program that I have attempted so far.. I have made up a handful of functions that I think would be useful as far as linked lists go.. I have coded up function prototypes... switch case menu.. and function definitions.

What I am looking for is simple...

I would like for someone to "fill in the gaps" of this program... complete a full example code that I can study.. so I can move on to bigger things (such as circularly linked lists and binary trees)

I would like just to be able to iterate forward and backward through a list of information.. be able to search for specific information.. and be able to insert and delete specific nodes.. and maybe make and display a copy of the current list.

Or... if you could post your own example code of how a basic linked list can be manipulated. :)

Either way will be fine for me.. and hopefully this thread will be of help for many others out there who are having the same problems with linked lists as I have. I will consider any answer provided groundbreaking... and I will take this knowledge and run with it.

Anyway.. here is what I've come up so far.. I call this program my, "linked list toolkit"

Code:

---

//My Linked List Toolkit



#include<cstdlib>        //Provides "EXIT_SUCCESS" and "system( )"
#include<string>        //Provides the "string" type qualifier
#include<iostream>        //Provides "cin" and "cout"
       
using namespace std;



/******* Linked List Function Prototypes *********/

void list_head_insert(node*& head_ptr, const node::double& entry);

void list_tail_insert(node*& head_ptr, const node::double& entry);

void list_insert(node* previous_ptr, const node::value_type& entry);

void list_remove(node* previous_ptr);

const node* list_search(const node* head_ptr, const node::value_type& target);

node* list_locate(node* head_ptr, int position);

void view_list(node* head_ptr);

int list_length(const node* head_ptr):

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

void list_clear(node*& head_ptr);

void list_head_remove(node*& head_ptr);

/******* Other Functions *********/

void print_menu();

void exit_message();





//prototype for my list

struct node
{
    string employee_name;
    int    phone_number;

    node *next_ptr;
    node *previous_ptr;
}   




int main()
{

char choice = 'x';


        do
        {
       
       
                print_menu();
                cin >> choice;
                switch(choice)
                {
               
                        case 1:        list_head_insert();
                                break;

                        case 2:        list_tail_insert();
                                break;

                        case 3:        void list_insert();
                                break;
               
                        case 4:        list_remove();
                                break;

                        case 5:        list_search();
                                break;

                        case 6:        list_locate();
                                break;

                        case 7:        view_list();
                                break;

                        case 8:        list_length();
                                break;

                        case 9:        list_copy();
                                break;

                        case 9:        list_clear();
                                break;

                        case 11        list_head_remove();
                                break;

                        case 12        exit_message();
                                break;

               
                        default: cout << "Invalid Entry.  Please Try Again.";
                               

                }                       
               

        }while (choice != 12);


       

return EXIT_SUCCESS;

}



/******************** Function Definitions ************************/

void print_menu()
{

            cout        << endl << endl
                        << "\t\t*******************************************\n"
                        << "\t\t*              MAIN MENU                *\n"
                        << "\t\t*******************************************\n"
                        << "\t\t*                                        *\n"
                        << "\t\t*  1-> ADD to the front of the list      *\n"
                        << "\t\t*  2-> ADD to the  back of the list      *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t*  3-> INSERT a node                      *\n"
                        << "\t\t*  4-> DELETE a node                      *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t*  5-> SEARCH                            *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t*  6-> VIEW a specific node              *\n"
                        << "\t\t*  7-> VIEW entire list                          *\n"
                        << "\t\t*  8-> VIEW list LENGTH                  *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t*  9-> COPY the current list                  *\n"
                        << "\t\t* 10-> CLEAR the entire list              *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t* 11-> Remove HEAD node                  *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t* 12-> QUIT                              *\n"
                        << "\t\t*                                        *\n"
                        << "\t\t*******************************************\n"
                        << endl << endl;

}



void list_head_insert(node*& head_ptr, const node::double& entry)
{
        head_ptr = new node(entry, head_ptr);
}



void list_tail_insert(node*& head_ptr, const node::double& entry)
{
        tail_ptr = new node(entry, head_ptr);
}



void list_insert(node* previous_ptr, const node::value_type& entry)
{
        node *insert_ptr;

        insert_ptr = new node;

        insert_ptr->set_data(entry);

        insert_ptr->set_link(previous_ptr->link());                //Make the new node point to the node after insertion

        previous_ptr->set_link(insert_ptr);                        //Made the previous node point to the newly inserted node
}



void list_remove(node* previous_ptr)
{
        node *remove_ptr;

        remove_ptr = previous_ptr->link();

        previous_ptr->set_link(remove_ptr->link());

        delete remove_ptr;
}



const node* list_search(const node* head_ptr, const node::value_type& target)
{
        const node *cursor;

        for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())

                if (target == cursor->data())

                        return cursor;
       
        return NULL;
}




node* list_locate(node* head_ptr, int position)
{
        const node* cursor;

        cursor = head_ptr;

        for (int i = 1; (i < position) && (cursor != NULL): ++i)

                cursor = cursor->link();

        return cursor;
}




void view_list(node* head_ptr)
{
        const node *cursor;

        for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())

                cout << cursor->get_data(entry);        //or just "cout << entry" perhaps?
}



int list_length(const node* head_ptr)
{
        const node *cursor;
       
        int answer = 0;

        for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
               
                ++answer;

        return answer;
}


//I would like the copy of the linked list to be displayed next to the original list when view_list() is called

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
{
        head_ptr = NULL;
        tail_ptr = NULL;

        //Handle the case of the empty list
        if (source_ptr == NULL)
                return;

        //Make the head node for the newly created list and put data in it.
        list_head_insert(head_ptr, source_ptr->data());
        tail_ptr = head_ptr;

        //Copy the reast of the nodes one at a time, adding at the tail of the new list
        source_ptr = source_ptr->link();
        while (source_ptr != NULL)
        {
                list_insert(tail_ptr, source_ptr->data());
                tail_ptr = tail_ptr->link();
                source_ptr = source_ptr->link();
        }
}


void list_clear(node*& head_ptr)
{
        while (head_ptr != NULL)

                list_head_remove(head_ptr);
}



void list_head_remove(node*& head_ptr)
{
        node *remove_ptr;

        remove_ptr = head_ptr;
       
        head_ptr = head_ptr->link();
       
        delete remove_ptr;
}


void exit_message()

{
        cout << "\n\tProgram will now terminate " << endl;
}

---

I believe that being able to manipulate a linked list using these types of functions will provide basic groundwork for linked list manipulation. I hope one of you out there will be willing to just maybe put the pieces of the puzzle together.

Feel free to use, "artistic liscense" as necessary.. make any changes you need.. (like the parameter lists) This code is mainly just a skeletal outline of something I envisioned as something that could actually work someday.

So here it is... my cry for help. Anything you guys can provide will be definately appreciated. :)

The problem with linked lists is that they're so varied. Even if you stick to single linked, non-circular lists there's a wealth of different ways of implementing them. The most common from what I've seen is a null pointer terminated list that doesn't use a dummy head or tail node. The code I've posted below reflects that.

Quote:

---

I would like just to be able to iterate forward and backward through a list of information.. be able to search for specific information.. and be able to insert and delete specific nodes.. and maybe make and display a copy of the current list.

---

The following is a double linked list that handles insertion and removal of various kinds, as well as a test print function. With the methods provided, you should have no trouble writing search routines, copy routines, or just about anything else you'll need. If you need clarification on any part of the code, don't hesitate to ask. :)

Code:

---

#include <iostream>
#include <string>

using namespace std;

struct node {
  string  data;
  node  *prev;
  node  *next;
public:
  node(const string& init, node *p, node *n)
    : data(init)
    , prev(p)
    , next(n)
  {}
};

struct list {
  node  *head;
public:
  list()
    : head(0)
  {}
};

void push_front(list& l, const string& data);
void push_back(list& l, const string& data);
void pop_front(list& l);
void pop_back(list& l);
void insert_after(list& l, node* it, const string& data);
void remove_this(list& l, node* it);
void show_list(list& l);

int main()
{
  list l;

  push_front(l, "test1");
  show_list(l);
  push_front(l, "test2");
  show_list(l);
  push_back(l, "test3");
  show_list(l);
  push_back(l, "test4");
  show_list(l);
  pop_front(l);
  show_list(l);
  pop_back(l);
  show_list(l);
  insert_after(l, l.head->next, "test5");
  show_list(l);
  remove_this(l, l.head->next);
  show_list(l);
}

void push_front(list& l, const string& data)
{
  if (!l.head) {
    l.head = new node(data, 0, 0);
  }
  else {
    node *new_node = new node(data, l.head->prev, l.head);
    l.head->prev = new_node;
    l.head = new_node;
  }
}

void push_back(list& l, const string& data)
{
  if (!l.head) {
    push_front(l, data);
  }
  else {
    node *it = l.head;
    while (it->next) {
      it = it->next;
    }
    node *new_node = new node(data, it, it->next);
    it->next = new_node;
  }
}

void pop_front(list& l)
{
  if (!l.head) {
    return;
  }
  else {
    node *old_node = l.head;
    l.head = l.head->next;
    if (l.head) {
      l.head->prev = 0;
    }
    delete old_node;
  }
}

void pop_back(list& l)
{
  if (!l.head) {
    return;
  }
  else {
    node *it = l.head;
    while (it->next) {
      it = it->next;
    }
    node *old_node = it;
    if (it->prev) {
      it->prev->next = it->next;
    }
    delete old_node;
  }
}

void insert_after(list& l, node* it, const string& data)
{
  if (!l.head) {
    push_front(l, data);
  }
  else {
    node *new_node = new node(data, it, it->next);
    if (it->next && it->next->prev) {
      it->next->prev = new_node;
    }
    it->next = new_node;
  }
}

void remove_this(list& l, node* it)
{
  if (!it) {
    return;
  }
  else if (it == l.head) {
    pop_front(l);
  }
  else {
    if (it->prev) {
      it->prev->next = it->next;
    }
    if (it->next) {
      it->next->prev = it->prev;
    }
    delete it;
  }
}

void show_list(list& l)
{
  node *it;

  cout<<"Forward: ";
  for (it = l.head; it->next; it = it->next) {
    cout<< it->data <<"->";
  }
  cout<< it->data <<endl;
  cout<<"Reverse: ";
  for (; it->prev; it = it->prev) {
    cout<< it->data <<"->";
  }
  cout<< it->data <<endl;
}

---

If you save a tail node then working with the end of the list is more efficient, but it's harder to maintain tail nodes. If a dummy header is used, it tends to simplify the logic, but it requires more setup in the constructor. The dynamic aspect of linked lists can be daunting until you realize that they're dynamic only in very specific and easily predicted ways. :)

very cool.. i think this is just what I've been looking for..

time to study ;)

Here is a little program i came up with.. with the help of my book. The only thing that really throws me is the copy constructor.. which is amoung the most complex i've seen.

This program is a stack using linked list data structure. The stack is created via head insert algorithm. It will prompt the user to enter a line of text. Each character will be dedicated it's own node when entered into the stack. The program will then cout the stack... which will display the user entry in reverse order.

Example:

Enter a word: drawer

Written backwards that is: reward

Again? (y/n):

Code:

---

#include<iostream>
using namespace std;

struct StackFrame
{
        char data;

        StackFrame *link;
};


typedef StackFrame* StackFramePtr;



class Stack
{

public:

        Stack();

        Stack(const Stack& a_stack);

        ~Stack();

        void push(char the_symbol);

        char pop();

        bool empty() const;

private:

        StackFramePtr top;

};



int main()
{

        Stack s;
       
        char next, ans;


        do
        {

                cout << "Enter a word: ";
               
                cin.get(next);

                while (next != '\n')
                {

                        s.push(next);

                        cin.get(next);

                }

            cout << "Written backward that is: ";
               
                while ( ! s.empty() )
                        cout << s.pop();

                cout << endl;


                cout << "Again? (y/n): ";

                cin >> ans;

                cin.ignore(10000, '\n');

        }while (ans != 'n' && ans != 'N');


        return 0;

}


//Function Definitions

Stack::Stack() : top(NULL)
{ }


Stack::Stack(const Stack& a_stack)
{

        if (a_stack.top == NULL)
                top = NULL;

       
        else
        {

                StackFramePtr temp = a_stack.top;  //temp moves through the nodes from top to bottom of a_stack

                StackFramePtr end;  //Points to end of the new stack;

               
                end = new StackFrame;

                end->data = temp->data;

                top = end;
                //First node crated and filled with data.
                //New nodes are now added AFTER this first node.


                temp = temp->link;

                while (temp != NULL)
                {

                        end->link = new StackFrame;

                        end = end->link;

                        end->data = temp->data;

                        temp = temp->link;
                }

                end->link = NULL;
        }

}



Stack::~Stack()
{
        char next;

        while (! empty() )
                next = pop();  //pop calls delete.

}



bool Stack::empty() const
{
        return (top == NULL);
}


void Stack::push(char the_symbol)
{

        StackFramePtr temp_ptr;

        temp_ptr = new StackFrame;



        temp_ptr->data = the_symbol;



        temp_ptr->link = top;

        top = temp_ptr;

}


char Stack::pop()
{
       
        if (empty())
        {
               
                cout << "Error: popping an empty stack.\n";
                exit(1);

        }

        char result = top->data;


        StackFramePtr temp_ptr;

        temp_ptr = top;

        top = top->link;


        delete temp_ptr;


        return result;

}

---

I just have a couple of questions aboot this code..


1.) why write this

Code:

---

Stack::Stack() : top(NULL)
{ }

---

when it's just the same thing as this:

Code:

---

top = NULL;

---

It seems more confusing to write it the first way.. i think because the colon makes it look like some sort of inherited member function.


2.) If someone could explain how the copy constructor works in this program.. that would be mad wicked cool. Specifically, what exactly is the a_stack variable.. :confused: additionally, is the copy constructor initializing the first node of the list... or does it initiallize every node that is added to the list..??

Code:

---

//copy constructor

Stack::Stack(const Stack& a_stack)
{

        if (a_stack.top == NULL)
                top = NULL;

       
        else
        {

                StackFramePtr temp = a_stack.top;  //temp moves through the nodes from top to bottom of a_stack

                StackFramePtr end;  //Points to end of the new stack;

               
                end = new StackFrame;

                end->data = temp->data;

                top = end;
                //First node crated and filled with data.
                //New nodes are now added AFTER this first node.


                temp = temp->link;

                while (temp != NULL)
                {

                        end->link = new StackFrame;

                        end = end->link;

                        end->data = temp->data;

                        temp = temp->link;
                }

                end->link = NULL;
        }

}

---

1) In this case there's really no difference. But it's good practice to use the initializer list for constructors whenever you can. It never hurts and is sometimes a necessity, such as when initializing const or reference members.

2) a_stack is the stack object that's being copied. The algorithm builds a new list with this->top as the head node and then uses end to as a tail pointer so that adding new nodes to the list is more efficient. temp walks down the stack to be copied so that the values can be copied. So a_stack is the stack to copy, temp is the iterator for a_stack's linked list and end is an iterator for *this's linked list so that a new node can be easily added to the end. To get a feel for how it works, do a paper run and execute each line of code, making sure to write down what values each variable will have at each line.

very cool :cool:

thanks again for thy mad knowledge