Thread: Singly Linked Lists: Clarification Needed

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    10

    Singly Linked Lists: Clarification Needed

    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:
      Code:
      // 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?



  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Your descriptions of Front, Curr, and Back seem off to me. I would think of all nodes in the list as nodes. I imagine them all linked together one after another with their "next" pointers. The node that doesn't have anybody else's "next" pointer pointing to it is special, and is the front. A node whose "next" pointer points to null is special in that it is the back. However, all nodes are still just nodes.

    Since you have to know where the nodes are in memory, you store a Front pointer that points to the front node. You don't really need a Back pointer for the back node in a singly linked list. The Curr pointer is just a temporary pointer that can point at any node (Front, Back, or other) while you are iterating through the list.

    Your explanation of looping sounds correct. You might even start with curr = front; and then you are always doing curr = curr->next to get to the next node, even for the second node in the list.

  3. #3
    Registered User
    Join Date
    Aug 2006
    Posts
    10
    The Curr pointer is just a temporary pointer that can point at any node (Front, Back, or other) while you are iterating through the list.
    That's interesting. I'm trying to escape the concept I have of sequential containers. There are two problems I'm having with this so far. The first is that I don't know how to designate a name for a linked list (or even if that's possible). The second is that I don't know how to view the elements of the linked list (are nodes synonymous with elements in this case?)
    I know that arrays, vectors, and lists are basically like this:
    [Element 0][Element 1][Element 2][Element 3][Element 4]etc...

    The way that we designate each element is by their number. Therefore, hypothetically, if I had a vector and wanted to access the Nth element, I'd just go
    Code:
    vector <int> v;
    
    // write code to assign initial values for vector v
    
    cout << v[5];
    This would then give me the value of the 5th element in this vector. How do I do that in the case of Linked lists?

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by jedispy
    That's interesting. I'm trying to escape the concept I have of sequential containers. There are two problems I'm having with this so far. The first is that I don't know how to designate a name for a linked list (or even if that's possible). The second is that I don't know how to view the elements of the linked list (are nodes synonymous with elements in this case?)
    I know that arrays, vectors, and lists are basically like this:
    [Element 0][Element 1][Element 2][Element 3][Element 4]etc...
    Linked list elements do have an order, but the memory structure is as follows:
    LinkedList->node(Element1,*next)->node(Element2,*next)->node(Element3,Null)

    lists are implemented as linked lists, so they work simmilarly internally, but STL does not reveal that to you.

    This would then give me the value of the 5th element in this vector. How do I do that in the case of Linked lists?
    Code:
    Node *cur=mylist.start
    for(i=0;i<5;i++)
        cur=cur->next;
    return cur->nodeValue;
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> I don't know how to designate a name for a linked list
    For each linked list you need to keep a pointer to the front. That is where you can name each list, by giving each separate Front pointer a different name.

    >> I know that arrays, vectors, and lists are basically like this: The way that we designate each element is by their number.
    Don't think of elements as having an index. In other words, don't think of element number 5. Linked lists don't work well that way because there is no easy and fast access to a specific element. You have to go through each element one at a time to get to element #5. Instead, think of a list as only a collection of objects. You use a list when you don't need to work on only one of the element, but rather you will need to work on all of them.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 01:01 AM
  2. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  3. Linked list of linked lists???
    By Qui in forum C++ Programming
    Replies: 6
    Last Post: 03-28-2004, 01:13 PM
  4. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  5. Linked lists and file i/o, and some other stuff
    By ninja in forum C++ Programming
    Replies: 9
    Last Post: 05-19-2002, 07:15 PM