Singly Linked Lists: Clarification Needed

[jedispy]

O.k. here's the usual stuff first:

• Compiler = Visual C++ 6.0
• OS = WinXP
• Part of a school assignment: Not directly
• Using the following class:

  // linked list node
  template <typename T>
  class node
  {
     public:
        T nodeValue;      // data held by the node
        node<T> *next;    // next node in the list
  
        // default constructor with no initial value
        node() : next(NULL)
        {}
  
        // constructor. initialize nodeValue and next
        node(const T& item, node<T> *nextNode = NULL) : 
  			  nodeValue(item), next(nextNode)
        {}
  };

I'm working on an assignment where I'm supposed to use linked lists. I'm really having a hard time understanding how they work and all that. For the assignment I'm doing I only need to use a singly linked list.

The main issue I'm running into is that I don't understand linked lists. I'm well familiar with sequential data structures.

Here's how I understand it. Please correct me if I'm wrong on this.

The elements of the singly linked list are as follows:

• Front // Front element in the list
• Curr // All elements in the list that are not Front and/or Back
• Back // Back element in the list

Now if a linked list has 10 elements, the the way I'd reference the elements is as follows:

• To access (insert/modify/delete) the second element in the linked list, I would refer to front->next.
• Then to I would then make a comment like curr = front->next; assigning the nodeValue of the second element to curr.
• To access the third element I would do the same thing. curr = curr->next;
• Then so on and so forth.

Does this sound correct to anyone?

[jfaust]

Sounds good to me! I think you're on the right track.

If you get tripped up with the code, let us know.

Jeff

[jedispy]

I guess the #1 thing that is tripping me up is whether or not there is a way to designate a name to the linked list. The assignment I'm working on calls for a basic algorithm to take the elements from one linked list, copy them sequentially to a second linked list. If this was just a standard list data structure, I would do something like this:

// This is just an example.  I have not checked this code for errors

list <int> mylist1, mylist2;

mylist1.push_back(1);  // Assign initial values in mylist1
mylist1.push_back(2);
mylist1.push_back(3);
mylist1.push_back(4);
mylist1.push_back(5);

int listsize = mylist1.size();  // Assigns value of mylist1.size() to listsize

for (int i = 0; i < listsize; i++)
{
     mylist2.push_back(mylist1.front());  // Assigns value of mylist1.front() to mylist2.back()
     mylist1.push_back(mylist1.front()); // Copies value of mylist1.front() to mylist1.back()
     mylist1.pop_front();  // Removes front of mylist1
}

In the above example, I have given names to the two lists. Essentially I'm supposed to do the same thing as in the example above, but using linked lists. When/where/how do I declare the names of the linked lists? If I don't do that, then how do I differentiate from one list to the next?

[screetch]

the head is commonly referred to as the list itself. If you have a pointer on the head, store it somewhere and don't lose it, the head will remain known as "the list"

a pop_front stuff changes the list, the new list is the new head.

If you prefer, create a class List which contains the head, that way you won't lose the head. It is the only data, so just pass it by copy as you would do with a std::list or std::vector.

[Paul McKenzie]

I guess the #1 thing that is tripping me up is whether or not there is a way to designate a name to the linked list.

A linked list consists of nodes. That should be a clue:

template <typename T> 
class linked_list
{
    private:
          node<T> headnode;

    public:
          void AddNode(const T&value)
          {
              // code to add value to headnode;
          }
};

int main()
{
     linked_list<int> list1, list2;
}

Regards,

Paul McKenzie