How to Implement very basic Linked List

[asad393]

How should i implement the very basic singly linked list in C++, i am having a paper in just 20 days and i dont know a bit about this stuff,,,

How to add data to it ,, as there is only one data item in single linked list and one pointer, how to accesss and remove data...

[Gonbe]

You know that a linked list is basically a value and a pointer to the next element in the list. (if any) So somewhere you define what the starting point of your linked list is. (the head) With that you can access every element in the list by using the pointers. Adding data is relatively easy too, because you work with pointers. Say you have a list containing "2->10" and you want to add "5" in the middle. Then you're have to let the pointer of "2" point to "5" and the pointer of "5" point to "10" so you get 2->5->10. Removing data is similar. It's all pretty simple, you just need to code the functions.

[Ancient Dragon]

Here is a beginners guide to linked lists tutorial.

[Gonbe]

Quick example: (can be infinitely improved, but "meh")

#include <iostream>
#include <stdexcept>

using namespace std;

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

typedef ListItem* pListItem;

// Should use templates.
// Just used as a shell for some operators, if you need the logic look at the private member functions.
class LinkedList
{
    public:
        // Constructors.
        LinkedList();

        // Member functions.
        void PushBack (const int value);
        void Remove   (const int value);
        int  Size     () const;

        // Member operators.
        int&       operator[] (const int index);
        const int& operator[] (const int index) const;

        // Friend functions.
        friend ostream& operator<< (ostream& stream, const LinkedList list);

    private:

        // Private member functions.
        void Add    (pListItem& list, const int value);
        void Remove (pListItem& list, const int value, const pListItem previous);
        int& At     (const pListItem list, const int index) const;
        int  Size   (const pListItem list) const;

        // Private member variables
        pListItem head;
};


LinkedList::LinkedList() : head(NULL)
{
}


void LinkedList::Add(pListItem& list, const int value)
{
    // Empty list!
    if (list == NULL)
    {
        // Create the item.
        list = new ListItem;

        // Set the values.
        list->next  = NULL;
        list->value = value;
    }
    else
    {
        Add(list->next, value);
    }
}


void LinkedList::PushBack(const int value)
{
    Add(head, value);
}


void LinkedList::Remove(const int value)
{
    Remove(head, value, NULL);
}


int LinkedList::Size() const
{
    return Size(head);
}


ostream& operator<< (ostream& stream, const LinkedList list)
{
    stream << "[";
    for (pListItem current = list.head; current != NULL; current = current->next)
    {
        if (current != list.head)
        {
            stream << ",";
        }

        stream << current->value;
    }
    stream << "]";

    return stream;
}


int& LinkedList::operator[] (const int index)
{
    return At(head, index);
}


const int& LinkedList::operator[] (const int index) const
{
   return At(head, index);
}


int& LinkedList::At(const pListItem list, const int index) const
{
    if (list == NULL)
    {
        throw out_of_range("index out of range on calling \"At\".");
    }
    else if (index == 0)
    {
        return list->value;
    }
    else
    {
        return At(list->next, index - 1);
    }
}


void LinkedList::Remove(pListItem& list, const int value, const pListItem previous)
{
    pListItem target = NULL;

    // Can't delete anything from an empty list.
    if (list != NULL)
    {
        // The list has the value
        if (list->value == value)
        {
            target = list;

            // The 2nd node is now the list.
            list = list->next;

            // If we had a previous node, update its pointer.
            if (previous != NULL)
            {
                previous->next = list;
            }

            // Delete the target node.
            delete target;
        }
        else
        {
            // Try to remove the value from the rest of the chain.
            Remove(list->next, value, list);
        }
    }
}


int LinkedList::Size(const pListItem list) const
{
    if (list == NULL)
    {
        return 0;
    }
    else
    {
        return 1 + Size(list->next);
    }
}


int main()
{
    LinkedList list;

    // Fill the linked list with value 1-10.
    for (int i = 1; i <= 10; i++)
        list.PushBack(i);

    // Remove the uneven elements
    for (int i = 1; i <= 10; i+=2)
        list.Remove(i);

    // Set the first value to "123".
    list[0] = 123;

    // Print the contents of the linked list.
    cout << "Our list has size " << list.Size() << " and it's contents are " << list << endl;

    return 0;
}

[Chilton]

@Gonbe: Why'd you give out an answer? This seems like an assignment, so why not let him/her do the work themselves and post it here if they need additional help?

[Gonbe]

I'm just bored. Besides, on a topic this common implementations can be found all-over anyway; if he wants code to copy he can/will get it. I always assume people don't mindlessly copy-paste things. If they do, it's their choice and it'll bite them in the ass at some point. The code present in the beginners guide ancient dragon linked could be copied as well.

-edit-
As this is subject I've seen multiple times in a short timespan, maybe I should improve and extend the above example and post it as a code snippet or whatever? (Maybe a C version would be more useful)