Any improvements over my linked-list method?

Question

I am continually writing a program to improve my knowledge of linked-lists and how they function. I was wondering if some of you could review my code and notice any faults that you may be familiar with, or any errors in general. The functions work for my test functions, but obviously, I have not tested every scenario possible.

    // LinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

struct node
{
    int value;
    node* next;
};

node* push(node*, int);
node* pop(node*);
node* pop(node*, int);
node* insert(node*, int, int);
void printList(const node*);

int _tmain(int argc, _TCHAR* argv[])
{
    node* head = NULL;

    for(int i = 1; i <= 15; ++i)
    {
        head = push(head, i);
    }

    for(int j = 14; j >= 0; j = j - 2)
    {
        head = pop(head, j);
        printList(head);
    }

    head = pop(head);
    head = insert(head, 4, 27);
    printList(head);
    cin.ignore();
}

node* push(node* read, int val)
{
    node* write = read;
    if(read == NULL)
    {
        read = new node;
        read->next = NULL;
        read->value = val;
        cout << "Node Head: " << read->value << endl;
        return read;
    }
    else
    {
        while(read->next != NULL)
        {
            read = read->next;
        }
        read->next = new node;
        read->next->next = NULL;
        read->next->value = val;
        read = read->next;
        cout << "Node Link: " << read->value << endl;
        return write;
    }
}

node* pop(node* read)
{
    node* write = read;
    if(read->next == NULL)
    {
        delete read;
        read = NULL;
        return write;
    }
    else
    {
        while(read->next != NULL)
        {
            if(read->next->next == NULL)
            {
                cout << "Pop: " << read->next->value << endl;
                delete read->next;
                read->next = NULL;
            }
            else
            {
                read = read->next;
            }
        }
        return write;
    }
}

node* pop(node* read, int pos)
{
    node* write = read;
    if(read->next == NULL)
    {
        delete read;
        return write;
    }
    else
    {   
        if(pos == 0)
        {
            node* old = read;
            cout << "Pop: " << read->value << endl;
            read = read->next;
            delete old;
            return read;
        }
        else
        {
            for(int i = 0; i < (pos - 1); i++)
            {
                read = read->next;
            }
            node* old = read->next;
            cout << "Pop: " << old->value << endl;
            read->next = read->next->next;
            delete old;
            return write;
        }
    }
}

node* insert(node* read, int pos, int val)
{
    node* write = read;
    for(int i = 0; i < (pos - 1); i++)
    {
        read = read->next;
    }
    node* ins = new node;
    ins->value = val;
    cout << "Insert: " << ins->value << endl;
    ins->next = read->next;
    read->next = ins;
    return write;
}

void printList(const node* read)
{
    if(read != NULL)
    {
        cout << "List Item: " << read->value << endl;
        printList(read->next);
    }
}

/****************OUTPUT*********************
Node Head: 1
Node Link: 2
Node Link: 3
Node Link: 4
Node Link: 5
Node Link: 6
Node Link: 7
Node Link: 8
Node Link: 9
Node Link: 10
Node Link: 11
Node Link: 12
Node Link: 13
Node Link: 14
Node Link: 15
Pop: 15
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 11
List Item: 12
List Item: 13
List Item: 14
Pop: 13
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 11
List Item: 12
List Item: 14
Pop: 11
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 12
List Item: 14
Pop: 9
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 7
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 5
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 3
List Item: 1
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 1
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 14
Insert: 27
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 27
List Item: 10
List Item: 12
*******************************************/

Answer 1

If a user can remove a node at a certain position, I don't think it can properly be called "pop." Pop usually refers to removing just the top node, like in a stack. "remove" would probably be a better name.

Answer 2

Well, first of all, for general use, you should be using the Standard library : std:vector, or, if you really need a linked-list, std::list<>. But, since this is a self-teaching exercise, we'll skip that.

Which bring us to the next problem: As a teaching exercise, it really isn't production code, so what things should we complain about? The cout's in the middle of functions??

One particular problem I saw was code like this:

    read = new node;    
    read->next = NULL;    
    read->value = val; 

The constructor for the node object should handle setting it's next member to null. For that matter it should handle setting the value also, so that this code should really be:

    read = new node(val);

Another problem: In pop(), you have:

node* write = read; 
if(read->next == NULL) 
{ 
    delete read; 
    read = NULL; 
    return write; 
} 

Setting read to null is pointless -- it's a local varaible about to go out of scope. And you are returning write, which is equal to read, which has beed deleted.

Additionally, you use almost no features of C++ and Object-oreitned programming in the code: If we ignore the cout's, it's basically just C code that's allocating memory via new & delete. As I noted, it could greatly benefit from a constructor. A destructor may be useful as well, plus a List class, which would hold the head node, and would have all your functions as members.

Answer 3

Looking just at your "push" function, here are a few suggestions:

• the 1st parameter should be named "head", not "read", for clarity

• there's a lot of duplication between the 2 branches of the "if(read == NULL)" test. Factor out the common code (for example, using a constructor as suggested by @James)

• break down the steps you're doing into something like "create a node with value 'val'", "find the end of the list", "if empty list, head = new; else tail->next = new"

Answer 4

You are making the list C-style. In C++ you would use a class for the Node and another class for the list. The class for the list should have a member for the first element in the list. Then, there are quite some mistakes here and there. I didn't get to review all the code but I can give you some pointers:

• always check the boundaries, cover all cases. What happens if I give an invalid pos (>size) ? :

   node* insert(node* read, int pos, int val)
    {
       node* write = read;
       for(int i = 0; i < (pos - 1), read <> NULL; i++) 
       {// you should make the for stop if it hits the bottom of the list
           read = read->next; 
       }
       if (read == NULL) return NULL
       node* ins = new node;
       ins->value = val;
       cout << "Insert: " << ins->value << endl;
       ins->next = read->next;
       read->next = ins;
       return write;
   }
  

• be careful with the memory and how you use it. Try as much as possible to avoid constructions like node->next->next as they are very error prone.

    node* pop(node* read)
    {
        node* write = read;
        if(read->next == NULL)
        {
            delete read;
            read = NULL;
            return write;
        }
        else
        {
            while(read->next != NULL)
            {
                if(read->next->next == NULL)
                {
                    cout << "Pop: " << read->next->value << endl;
                    delete read->next;
                    read->next = NULL;
                }
                else
                {
                    read = read->next;
                }
            }
            return write;
        }
    }
  

Could be simply written like this:

     node* pop(node* head)
     {
        if (head == NULL) return;

        node* previous = NULL;
        node* returnVal = head;

        while (head->next != NULL)
        {
            previous = head;
            head = head->next;
        }
        if (previous != NULL)
        {
            previous->next = NULL;
            delete head;
        }
        else //we need to pop out the head :)
        {
            delete head;
            returnVal = null;
        }
        return returnVal;
     }

It's a bit confusing not to have a global member of the class pointing to the head of the list. I'm not used to that.. A C++ style list remove function would be written like this:

void SingleLinkedList::RemoveElement(TInfo value)
{
    Node* cursor = mHead;
    Node* lastCursor = NULL;

    if (cursor != NULL) while (cursor->GetNext() != NULL && cursor->GetInfo() != value) 
    {
        lastCursor = cursor;
        cursor = cursor->GetNext();
    }
    if (cursor->GetInfo() == value)
    {
        lastCursor->SetNext(cursor->GetNext());
        delete cursor;
    }
}

And the definition of the classes looks like this:

#define NULL 0
typedef int TInfo;

class Node
{
private:
    TInfo info;
    Node* next;
public:

    Node()                          {info = 0; next = NULL;}
    Node(TInfo iInfo, Node* iNode)  {info = iInfo; next = iNode;}
    ~Node()                         {info = 0; next = NULL;}

    TInfo GetInfo() const           {return info;}
    Node* GetNext() const           {return next;}

    void SetInfo(TInfo value)       {info = value;}
    void SetNext(Node* pValue)      {next = pValue;}
};

class SingleLinkedList
{
private:
    Node* mHead;
    int mCount;

    void RecursiveRemove(Node* iNode);

public:
    SingleLinkedList();
    ~SingleLinkedList() {mHead = NULL;};

    int Count() const               {return mCount;}
    Node* const GetHead() const     {return mHead;}

    void ClearList();
    void AddHeadElement(TInfo value);
    void AddTailElement(TInfo value);
    void RemoveElement(TInfo value);
    bool SearchElement(TInfo value, int &pos);
};

void PrintList (SingleLinkedList const& list);

There are many improvements that you can make to your code. Think simple :)

Answer 5

If you are making a C-style linked list class, you should use a void * for the data item, which will allow you use the linked list with other types:

struct Node
{
    void * p_data;
    struct Node * next;
};

On the other hand, if you want to use C++ facilities, you could expand to use a template for the data type. A template will allow you to use the same code for different types. The compiler will resolve the data type during instantiation of the template (stencil):

template <class Data_Type>
struct Node
{
    Data_Type data;
    Node *    next;
};

As other people have said, you should have a List class, or structure. This will help users distinguish instantiations. In the C-Style, this structure would be passed to the list methods (so the list methods know which list to operate on).

struct List_Header
{
    struct Node * head;
    struct Node * tail;
    unsigned int  size; // Quantity of nodes
};

void List_Push(List_Header * p_header, void * data)
{
  if (p_header)
  {
    // Create a node, prepend to list, etc.
  }
  return;
}

To use the list:

List_Header    my_list;
unsigned int *   my_data(new int(1));
List_Push(&my_list, my_data);