[Solved] How does a linked list with Node class work in C++?

by


A nice tutorial is at: http://www.zentut.com/c-tutorial/c-linked-list/

From a programming perspective, normally your LinkedList class would have some methods to do the things you asked about, for example:

  • Add – create a new entry at the end of the linked list
  • InsertAfter(Node *n) – create a new entry after indicated node in the listed list
  • Remove(Node *n) – removes the indicated node from the linked list
  • Count() – returns a count of the number of nodes within the linked list
  • Get(long i) – returns a pointer to the ith entry in the linked list
  • Find(some type of criteria) – return a pointer to the node that matches
  • Destroy – remove all the nodes in the linked list

Then your mainline just invokes these methods to utilize the linked list (the whole point of object encapsulation). Note that there is a LinkedList object instantiated, and it instantiates and manages the Node objects.

So if you had 10 numbers to store from some input array (inArray), you could do something like:

Node* n;
llObj = new LinkedList;
For (i=0; i<=9; i++) {
    n = llObj.add();
    n.data = inArray[i];
}

To step through the linked list, you would do something like:

For (i=0; i<=llObj.Count(); i++) {
    n = llObj.get(i);
    n.data = n.data + 1;
}

However, if you write yourself a .get() method from the code samples below, you will see that above code is terribly inefficient, and is not the ideal way to step through the entire linked list from mainline code.

To find the number 6:

n = llObj.find(6);

And so forth. Normally a linked list does not store just one data value such as in your example, but rather stores a structure or an object. Hence methods like Find become more useful because you can create Find methods that look at various fields in a structure or an object.

An Add method just traverses all the existing entries in the listed list until the last one is found, then creates a new entry, and links the former last entry to the now new last entry.

Node* LinkedList::add() {
    void *n = NULL;
    if (head != NULL) {
        // one or more Nodes do exist
        // first loop until we find the last-most node who's n.next == NULL
        n = head;
        while (n.next != NULL) n = n.next;
        // found the last node, now allocate a new Node, and store a pointer to it in the formerly last node's .next property
        n.next = new Node;
        n = n.next;
        // IMPORTANT: ensure this new last Node's .next is forced to be null
        n.next = NULL;
    }
    else
    {
        // the header is NULL, so there is no first node yet
        // allocate a new Node and store a pointer to it in the LinkedList header
        head = new Node;
        n = head;
        // IMPORTANT: ensure this first Node's .next is forced to be null
        n.next = NULL;  
    {
    return n;
}

Note the While loop … this is the key linked-list traversal mechanism. That loop checks the current node’s .next field … if it has a non-NULL pointer, then the loop cycles by copying that .next pointer to the loop pointer n, and tests again. Once the loop finds a node who’s .next is NULL, then the lastmost node has been found, and the loop exits, with n containing the pointer to that lastmost node.

Note also the If statement concerning the .head property of the LinkedList class. One always has to do some special code for accounting for when the linked list is empty. There are a couple of ways of handling that; I chose the one that uses the least data memory.

Removing a node means just “skipping over it” in the linked list. We traverse the listed list until we find the one to remove, the we just “move back” its .next property to the prior entry’s .next pointer. A good image is in the Linked List wikipedia entry: enter image description here

A code example:

void LinkedList::remove(Node* nodeToRemove) {
    // do nothing if we've been given a NULL pointer
    if (nodeToRemove == NULL) return;
    Node *n;
    if (nodeToRemove == head) {
        // the node to remove is the very first node, so set the head
        // to the contents of the first node's .next property
        head = n.next;
        delete n;
        return;
    }

    // need to find the indicated node; the following loop locates the
    // node that is immediately before the node to be removed; note too
    // that we have to test for the end of the linked list because the
    // caller may have provided a bad pointer value
    n = head;
    while (n.next != NULL && n.next != nodeToRemove) n = n.next;
    if (n.next == NULL) return;  // reached end of linked list without finding the node
    // good, the node immediately before the node to remove has been found!
    Node* r = n.next;   // this is inefficient code but want to make it very clear to newbies
    n.next = r.next;
   delete r;
}

Note that again we have to do some special logic concerning the LinkedList header. And do pardon the fact that I’ve used returns in the code; many finicky stickers would consider that a no-no. Also note in the code above, we don’t need to do special logic to account for the end of the linked list, only just its beginning. If the node-to-remove is the last node in the linked list (and its r.next therefore == NULL), then the “n.next = r.next” line of code just moves the NULL back one position in the linked list, which is exactly what we would want.

You should be able to now figure out how to create all those other methods in your LinkedList class that I mentioned.

===============================

I do like someone’s answer that unfortunately he deleted. For a 5 year old, a linked list is indeed a lot like the game of Treasure Hunt. In a Treasure Hint, you have to physically go to each location to get the clue to the next location. And in a linked list you have to access the location of a node to find the address of the location of the next node. A perfect analogy, and kudos for the answerer that first provided it.

0

solved How does a linked list with Node class work in C++?