Singly Linked Lists: Clarification Needed

Printable View

12-14-2006
jedispy

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?
12-14-2006
Daved

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.
12-14-2006
jedispy

Quote:

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?
12-14-2006
King Mir

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.

Quote:

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;
12-14-2006
Daved

>> 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.