链表是如何工作的？

Question

我正在阅读一个教程，我也在谷歌上搜索过，但我找不到关于链接列表如何工作的详细说明的很好的解释......我真的对结构/格式感到困惑，我真的希望链接列表有意义对我来说，它们听起来很棒，因为它们是一个可调整大小和可修改的数组……如果您需要了解我在说什么，下面是我从 tut 中获得的一些代码。我对追加方法或删除等方法、它们的作用以及列表中的尾头事物的工作方式感到困惑......这本书只是从一个例子开始，没有给出解释..

请帮助解决这个困惑..

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() 方法 FindFirst() 方法 FindNext() 方法 InsertBefore() 方法 InsertAfter() 方法

但是现在基本的都很好..

Answer 1

链表是用于收集对象序列的结构化数据。“头部”是序列中的第一个项目。“Tail”是序列中的最后一个对象。链表（一个节点）中的每一项都有一个名为 Next（如果是双向链接的，则为 Previous）的属性，它指向列表中的 Next 或 Previous 项。这些下一个和上一个项目只是指向集合中的下一个或上一个项目，因此要遍历它们，您必须按顺序进行。

把链表想象成链中的链接。要到达列表中的第 5 项，您可以从链中的第一个链接开始，然后按照它直到到达第 5 项。希望这有所帮助。

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