链表如何工作？ [英] How do linked list work?

问题描述

我正在阅读教程，也浏览了整个Google，但是找不到关于链表如何工作的详细说明...我对结构/格式感到很困惑，我真的希望链接列表对我来说很有意义，因为它们听起来很棒，是一个可调整大小和可修改的数组...下面是一些我从tut那里得到的代码，如果您需要了解我在说什么。我对诸如append method或delete之类的方法，它们的作用以及列表中尾部内容的工作方式感到困惑……这本书只是从一个示例开始，没有给出解释。.

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..

请帮助解决这个混乱。

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（）方法

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..

推荐答案

链表是一种用于收集对象序列。 头是序列中的第一项。 尾巴是序列中的最后一个对象。链接列表中的每个项目（节点）将具有一个名为Next（如果是双重链接，则为Previous）的属性，该属性指向列表中的Next或Previous项目。这些下一个和上一个项目仅指向集合中的下一个或上一个项目，因此要对其进行迭代，必须按顺序进行。

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.

请考虑链接列表像链中的链接。要获得列表中的第5个项目，请从链中的第一个链接开始，然后按照它进行操作，直到获得第5个项目。希望这会有所帮助。

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：// zh.wikipedia.org/wiki/Linked_list

这篇关于链表如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！