How do linked list work?

Question

I am reading a tutorial and I looked all over google as well but I can't find a good explaantion of details on how a linked list works...I am really confused about the structure/Format and I really wish linked list made sense to me as they sound great, being an array thats resizeable and modifiable...Below is some code I have from a tut if you need to see what I am talking about. I am confused about the methods such as append method or delete, what they do and how tail head thingy in list work...The book just starts with an example and doesn't give explanation..

Please help with this confusion..

class ListEntry
{
    int data;
    ListEntry next;

    public ListEntry( int d )
    {
        data = d;
        next = null;
    }

    public int Data
    {
        get{ return data; }
        set{ data = value; }
    }

    public ListEntry Next
    {
        get{ return next; }
        set{ next = value; }
    }

    public override string ToString( )
    {
        return( data.ToString( ) );
    }
}


class TestProgram
    {
        static void Main( )
        {
            List list = new List( );

            list.Append( 3);
            Console.WriteLine( list );

            list.Append( 1 );
            Console.WriteLine( list );

            list.Append( 6 );
            Console.WriteLine( list );

            list.Prepend( 4 );
            Console.WriteLine( list );

            // continued…

// Continued…

        list.Prepend( 5 );
        Console.WriteLine( list );

        list.DeleteFirst( 4 );
        Console.WriteLine( list );

        list.Prepend( 2 );
        Console.WriteLine( list );

        Console.WriteLine( "Head data = " + list.Head );
        Console.WriteLine( "Tail data = " + list.Tail );

        list.Clear( );
        Console.WriteLine( list );

        Console.WriteLine( "IsEmpty = " + list.IsEmpty );
    }
}



using System;

class List
{
    ListEntry head;
    ListEntry tail;

    class ListEntry
    {
        // Put declaration of ListEntry here.  Nesting of the classes is valid.  In fact, class nesting is
        // preferable if one class is only used within the context of another class.
    }

    public List( )
    {
        head = null;
        tail = null;
    }

    // Continued…


public int Head
{
    get{ return head.Data; }
}

public int Tail
{
    get{ return tail.Data; }
}

public bool IsEmpty
{
    get{ return( head == null ); } 
}

public override string ToString( )
{
    string tmp = "";

    ListEntry current = head;
    if( current == null )
    {
        tmp = "Empty";
    }
    while( current != null )
    {
        tmp += current + " ";
        current = current.Next;
    }
    return( tmp );
}

public void Append( int i )
{
    ListEntry tmp = new ListEntry( i );

    tmp.Next = null;

    if( head == null )
    {
        head = tmp;
    }
    else
    {
        tail.Next = tmp;
    }
    tail = tmp;
}

public void Prepend( int i )
{
    ListEntry tmp = new ListEntry( i );

    tmp.Next = head;

    if( head == null )
    {
        tail = tmp;
    }
    head = tmp;
}

public void DeleteFirst( int i )
{
    ListEntry current = head;
    ListEntry previous = null;

    while( current != null && current.Data != i )
    {
        previous = current;
        current = current.Next;
    }
    if( current == null )
    {
        throw new ArgumentException( "List entry not found" );
    }

    // Continued…


// Continued…

    if( current == head )
    {
        head = current.Next;
    }
    else
    {
        previous.Next = current.Next;
    }
    if( current == tail )
    {
        tail = previous;
    }
}

There are other methods such as : A Sort( ) method A FindFirst( ) method A FindNext( ) method An InsertBefore( ) method An InsertAfter( ) method

But for now the basic ones are fine..

Answer 1

A Linked List is a data structured used for collecting a sequence of objects. The "Head" is the very first item in the sequence. The "Tail" is the last object in the sequence. Each item in the linked list (a node) will have a property called Next (and Previous if it is doubly linked) which points to the Next or Previous item in the list. These next and previous items just point to the next or previous item in the collection, so to iterate over them you have to do it in order.

Think of a linked list like links in a chain. To get to the 5th item in the list, you start at the very first link in the chain and then follow it until you get to the 5th item. Hope this helps a little.

http://en.wikipedia.org/wiki/Linked_list

Answer 2

A simple singly-linked list implementation in C# (generic):

public class LinkedList<T>
{
    private Node<T> head;

    public void AddAtFront(T data)
    {
        this.head = new Node<T>(data, this.head);
    }

    public void AddAtBack(T data)
    {
        var node = new Node<T>(data);
        var current = this.head;

        if (current == null)
        {
            this.head = node;
        }
        else
        {
            while (current.Next != null)
            {
                current = current.Next;
            }

            current.Next = node;
        }
    }

    public Node<T> Front
    {
        get
        {
            return this.head;
        }
    }

    public Node<T> Back
    {
        get
        {
            var current = this.head;

            if (current != null)
            {
                while (current.Next != null)
                {
                    current = current.Next;
                }
            }

            return current;
        }
    }

    public Node<T> RemoveAtFront()
    {
        var node = this.head;

        if (node != null)
        {
            this.head = node.Next;
        }

        return node;
    }

    public Node<T> RemoveAtBack()
    {
        var current = this.head;

        if (current != null)
        {
            if (current.Next == null)
            {
                this.head = null;
            }
            else
            {
                Node<T> nextToLast = null;

                while (current.Next != null)
                {
                    nextToLast = current;
                    current = current.Next;
                }

                nextToLast.Next = null;
            }
        }

        return current;
    }
}

and

public class Node<T>
{
    private readonly T data;

    private Node<T> next;

    public Node(T data)
    {
        this.data = data;
    }

    public Node(T data, Node<T> next)
    {
        this.data = data;
        this.next = next;
    }

    public T Data
    {
        get
        {
            return this.data;
        }
    }

    public Node<T> Next
    {
        get
        {
            return this.next;
        }

        set
        {
            this.next = value;
        }
    }
}