链表是如何工作的
本文关键字：工作 何工作 链表 | 更新日期: 2023-09-27 18:04:50
我正在阅读一个教程，我在谷歌上看了很多，但我找不到一个很好的解释链表是如何工作的细节…我真的对结构/格式感到困惑，我真的希望链表对我有意义，因为它们听起来很棒，是一个可调整大小和可修改的数组…下面是一些代码，我从一个图坦卡蒙，如果你需要看看我在说什么。我对附加方法或删除等方法感到困惑，它们做什么以及列表中尾头的事情如何工作……这本书只是以一个例子开始，没有给出解释。
请帮助解决这个问题。
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()方法
链表是一种用于收集对象序列的数据结构。"Head"是序列中的第一项。"Tail"是序列中的最后一个对象。链表中的每个项(节点)都有一个名为Next(如果是双链接则为Previous)的属性，它指向列表中的Next或Previous项。这些下一项和前一项只是指向集合中的下一项或前一项，因此要对它们进行迭代，必须按顺序执行。
把链表想象成链上的链接。为了找到列表中的第5个项目，你从链中的第一个环节开始，然后沿着它一直到第5个项目。希望这对你有帮助。
http://en.wikipedia.org/wiki/Linked_list一个简单的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;
}
}
}