Как работает связанный список?

Question

Я читаю учебное пособие, и я тоже просмотрел весь гугл, но не могу найти хорошее объяснение подробностей о том, как работает связанный список ... Я действительно запутался в структуре / формате и мне очень хотелось бы связатьСписок имеет смысл для меня, так как они звучат великолепно, будучи массивом, который можно изменять и изменять в размерах ... Ниже приведен некоторый код, который я получил из статьи, если вам нужно понять, о чем я говорю.Я запутался в методах, таких как метод добавления или удаления, что они делают и как работает «хвостовая голова» в списке ... Книга только начинается с примера и не дает объяснения ..

Пожалуйста, помогитес этой путаницей ..

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;
    }
}

Существуют и другие методы, такие как: метод Sort () A метод FindFirst () A метод FindNext () метод InsertBefore () метод InsertAfter ()

Но пока с основными всё в порядке ..

Answer 1

Связанный список - это структура данных, используемая для сбора последовательности объектов.«Голова» - самый первый элемент в последовательности.«Хвост» - последний объект в последовательности.Каждый элемент в связанном списке (узле) будет иметь свойство Next (и Previous, если он дважды связан), которое указывает на следующий или предыдущий элемент в списке.Эти следующие и предыдущие элементы просто указывают на следующий или предыдущий элемент в коллекции, поэтому для их итерации необходимо выполнить их по порядку.

Думайте о связанном списке как о связях в цепочке.Чтобы добраться до 5-го элемента в списке, вы начинаете с самой первой ссылки в цепочке, а затем переходите по ней, пока не дойдете до 5-го элемента.Надеюсь, это немного поможет.

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

Answer 2

Простая реализация односвязного списка в C # (универсальная):

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;
    }
}

и

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;
        }
    }
}