Creating a Very Simple Linked List

Creating a very simple linked list

A Linked List, at its core is a bunch of Nodes linked together.

So, you need to start with a simple Node class:

public class Node {
    public Node next;
    public Object data;
}

Then your linked list will have as a member one node representing the head (start) of the list:

public class LinkedList {
    private Node head;
}

Then you need to add functionality to the list by adding methods. They usually involve some sort of traversal along all of the nodes.

public void printAllNodes() {
    Node current = head;
    while (current != null) 
    {
        Console.WriteLine(current.data);
        current = current.next;
    }
}

Also, inserting new data is another common operation:

public void Add(Object data) {
    Node toAdd = new Node();
    toAdd.data = data;
    Node current = head;
    // traverse all nodes (see the print all nodes method for an example)
    current.next = toAdd;
}

This should provide a good starting point.

Simple linked list in C++

This is the most simple example I can think of in this case and is not tested. Please consider that this uses some bad practices and does not go the way you normally would go with C++ (initialize lists, separation of declaration and definition, and so on). But that are topics I can't cover here.

#include <iostream>
using namespace std;

class LinkedList{
    // Struct inside the class LinkedList
    // This is one node which is not needed by the caller. It is just
    // for internal work.
    struct Node {
        int x;
        Node *next;
    };

// public member
public:
    // constructor
    LinkedList(){
        head = NULL; // set head to NULL
    }

    // destructor
    ~LinkedList(){
        Node *next = head;
        
        while(next) {              // iterate over all elements
            Node *deleteMe = next;
            next = next->next;     // save pointer to the next element
            delete deleteMe;       // delete the current entry
        }
    }
    
    // This prepends a new value at the beginning of the list
    void addValue(int val){
        Node *n = new Node();   // create new Node
        n->x = val;             // set value
        n->next = head;         // make the node point to the next node.
                                //  If the list is empty, this is NULL, so the end of the list --> OK
        head = n;               // last but not least, make the head point at the new node.
    }

    // returns the first element in the list and deletes the Node.
    // caution, no error-checking here!
    int popValue(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }

// private member
private:
    Node *head; // this is the private member variable. It is just a pointer to the first Node
};

int main() {
    LinkedList list;

    list.addValue(5);
    list.addValue(10);
    list.addValue(20);

    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    // because there is no error checking in popValue(), the following
    // is undefined behavior. Probably the program will crash, because
    // there are no more values in the list.
    // cout << list.popValue() << endl;
    return 0;
}

I would strongly suggest you to read a little bit about C++ and Object oriented programming. A good starting point could be this: http://www.galileocomputing.de/1278?GPP=opoo

EDIT: added a pop function and some output. As you can see the program pushes 3 values 5, 10, 20 and afterwards pops them. The order is reversed afterwards because this list works in stack mode (LIFO, Last in First out)

Creating a LinkedList class from scratch

If you're actually building a real system, then yes, you'd typically just use the stuff in the standard library if what you need is available there. That said, don't think of this as a pointless exercise. It's good to understand how things work, and understanding linked lists is an important step towards understanding more complex data structures, many of which don't exist in the standard libraries.

There are some differences between the way you're creating a linked list and the way the Java collections API does it. The Collections API is trying to adhere to a more complicated interface. The Collections API linked list is also a doubly linked list, while you're building a singly linked list. What you're doing is more appropriate for a class assignment.

With your LinkedList class, an instance will always be a list of at least one element. With this kind of setup you'd use null for when you need an empty list.

Think of next as being "the rest of the list". In fact, many similar implementations use the name "tail" instead of "next".

Here's a diagram of a LinkedList containing 3 elements:

Note that it's a LinkedList object pointing to a word ("Hello") and a list of 2 elements. The list of 2 elements has a word ("Stack") and a list of 1 element. That list of 1 element has a word ("Overflow") and an empty list (null). So you can treat next as just another list that happens to be one element shorter.

You may want to add another constructor that just takes a String, and sets next to null. This would be for creating a 1-element list.

To append, you check if next is null. If it is, create a new one element list and set next to that.

next = new LinkedList(word);

If next isn't null, then append to next instead.

next.append(word);

This is the recursive approach, which is the least amount of code. You can turn that into an iterative solution which would be more efficient in Java^*, and wouldn't risk a stack overflow with very long lists, but I'm guessing that level of complexity isn't needed for your assignment.

---

^{* Some languages have tail call elimination, which is an optimization that lets the language implementation convert "tail calls" (a call to another function as the very last step before returning) into (effectively) a "goto". This makes such code completely avoid using the stack, which makes it safer (you can't overflow the stack if you don't use the stack) and typically more efficient. Scheme is probably the most well known example of a language with this feature.}

C# singly linked list implementation

In a simple singly-linked list implementation the Node type contains a reference to the next item in the list, which is what the next field in the Node type you posted does. This reference is used to allow iteration of the list.

The enclosing LinkedList class (or whatever you wish to call it) will contain a single Node reference to the first item in the list. Starting from that first node you can then step through the list by getting the next field. When next is null then you have reached the end of the list.

Take this code for example:

public class LinkedList
{
    public class Node
    {
        // link to next Node in list
        public Node next = null;
        // value of this Node
        public object data;
    }

    private Node root = null;

    public Node First { get { return root; } }

    public Node Last 
    {
        get
        {
            Node curr = root;
            if (curr == null)
                return null;
            while (curr.next != null)
                curr = curr.next;
            return curr;
        }
    }
}

The First property simply returns the root node, which is the first node in the list. The Last property starts at the root node and steps through the list until it finds a node whose next property is null, indicating the end of the list.

This makes it simple to append items to the list:

public void Append(object value)
{
    Node n = new Node { data = value };
    if (root == null)
        root = n;
    else
        Last.next = n;
}

To delete a node you have to find the node that precedes it in the list, then update the next link from that node to point to the node following the one to be deleted:

public void Delete(Node n)
{
    if (root == node) 
    {
        root = n.next;
        n.next = null;
    }
    else
    {
        Node curr = root;
        while (curr.next != null)
        {
            if (curr.next == n)
            {
                curr.next = n.next;
                n.next = null;
                break;
            }
            curr = curr.next;
        }
    }
}

There are a few other operations you can perform, like inserting values at positions in the list, swapping nodes, etc. Inserting after a node is fast, before is slow since you have to locate the prior node. If you really want fast 'insert-before' you need to use a doubly-linked list where the Node type has both next and previous links.

---

To expand on your question in the comment...

In C# there are two basic classifications that all types fall into: value types and reference types. The names reflect the way they are passed between blocks of code: value types are passed by value (value is copied to a new variable), while reference types are passed by reference (a reference/pointer is copied to a new variable). The difference there is that changes to a value type parameter will have no effect on the caller's copy of the value, while changes to a reference type parameter will be reflected in the caller's copy of the reference.

The same is true of assigning values and references to variables. In the following, the value of a is not changed when b is changed:

int a = 0;
int b = a;
b = 1;

That's fairly intuitive. What might trip you up is that in C# a struct is also a value type:

public struct test
{
    public string value;
}

static void Main()
{
    test a;
    a.value = "a";
    test b = a;
    b.value = "b";

    Console.WriteLine("{0} {1}", a.value, b.value);
}

The above will give the output a b because when you assigned a to b a copy was made. But if we change the struct for a class:

public class test
{
    public string value;
}

static void Main()
{
    test a = new test(); // Note the 'new' keyword to create a reference type instance
    a.value = "a";
    test b = a;
    b.value = "b";
    Console.WriteLine("{0} {1}", a.value, b.value);
}

Because the variable b is a reference to the same object as the one variable a references, the output here will be b b. The two variables reference the same object.

If you've come from C/C++ or some other similar language, you can think of reference type variables as being pointers. It's not quite the same, and C# does actually have pointers (they're hidden from normal managed code), but it's close enough. Until you point it to an instance of the type it is not fully usable. Just like a char* in C/C++ isn't particularly useful until you point it somewhere.

Joseph Alhabari (has written a great article about value and reference types: C# Concepts: Value vs Reference Types. It is well worth a read, as is much of what he writes. I would also highly recommend you consider getting one of his C# Nutshell books.

How do you create a singly linked list with input in C++

You do not have to pass the size variable to the addNode Function. Just take values as much you desire in main funtion and pass them to addNode funtion by looping till the size, then add Nodes to the list as usual.
Your code will look something like this:

#include <iostream>
using namespace std;

struct Node{
    int data;
    int nodeNumber;
    Node *next;
};
Node *nodeHead=NULL;

void addNode (int num);
void displayNode();

int main(){
    int size, value;

    cout<<"Enter number of Nodes: ";
    cin>>size;

    for (int i=0; i<size; i++){
        cin>>value;
        addNode(value);
    }

    displayNode();
    system("pause>0");
}
 
void addNode(int num){
    Node *tail = nodeHead;
    Node *nodePtr = new Node;
    nodePtr->data = num;
    nodePtr->next = NULL;

    if (nodeHead == NULL){
        nodeHead = nodePtr;
    }
    else{
        while(tail->next != NULL){
            tail = tail->next;
        }
        tail->next = nodePtr;
    }
}

void displayNode(){
    Node *nodeTemp = new Node;
    nodeTemp = nodeHead;
    
    cout<<"The linked list: ";
    while(nodeTemp != NULL){
        cout<<nodeTemp->data<<" ";
        nodeTemp = nodeTemp->next;
    }
}

---

Related Topics