XIAOSUO 记录个人学习的足迹

一、结点为LinkedListNode​对象

该对象的实现如下

//在LinkedList<T>中LinkedListNode<T>相互之间构成双向环状链表
//该双向环状链表通过内部成员next、prev来实现，但对于外部不可见
//对于外部Next、Previous表现为双向链表，首尾不构成环
public sealed class LinkedListNode<T>
{
	internal LinkedList<T> list;
	internal LinkedListNode<T> next;
	internal LinkedListNode<T> prev;
	internal T item;

	public LinkedListNode(T value)
	{
		this.item = value;
	}

	internal LinkedListNode(LinkedList<T> list, T value)
	{
		this.list = list;
		this.item = value;
	}

	public LinkedList<T> List
	{
		get { return list; }
	}

	public LinkedListNode<T> Next
	{
		get { return next == null || next == list.head ? null : next; }
	}

	public LinkedListNode<T> Previous
	{
		get { return prev == null || this == list.head ? null : prev; }
	}

	public T Value
	{
		get { return item; }
		set { item = value; }
	}

	internal void Invalidate()
	{
		list = null;
		next = null;
		prev = null;
	}
}

二、外部表现为双向线性链表，内部实现实际为双向环状链表

通过LinkedListNode​的实现代码我们可以知道该对象对外通过Next,Previous对next，previous包装实现（Next,Previous均为只读），首尾不相接构成环。而对内next,prev声明为internal级别LinkedList​类将直接操作next,prev成员

public class LinkedList<T> : ICollection<T>, System.Collections.ICollection, ISerializable, IDeserializationCallback
{
	internal LinkedListNode<T> head;    //双向环状链表的第一个结点，
	internal int count;                 //结点个数
	internal int version;
　　　　 private SerializationInfo siInfo;   //临时变量，用于反序列化

//......其他成员

	public LinkedListNode<T> First
	{
		get { return head; }
	}

	//注意如何将内部表示的双向循环链表，外部体现的双向线性链表
	public LinkedListNode<T> Last
	{
		get { return head == null ? null : head.prev; }
	}
	//......其他代码
 }

三、插入、删除操作的实现

因为LinkedList​类对外体现为双向链表，对于插入操作有方法AddAfter，AddBefore，AddFirst，AddLast，删除操作拥有方法Remove，RemoveFirst，RemoveLast通过名称我们可以知道它们实现的功能，而这些方法的具体实现将分别调用3种辅助方法，代码如下

private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
	newNode.next = node;
	newNode.prev = node.prev;
	node.prev.next = newNode;
	node.prev = newNode;
	version++;
	count++;
}

//向空链表插入第一个结点
private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
{
	Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!");
	newNode.next = newNode;
	newNode.prev = newNode;
	head = newNode;
	version++;
	count++;
}

internal void InternalRemoveNode(LinkedListNode<T> node)
{
	Debug.Assert(node.list == this, "Deleting the node from another list!");
	Debug.Assert(head != null, "This method shouldn't be called on empty list!");
	if (node.next == node)
	{
		Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node");
		head = null;
	}
	else
	{
		node.next.prev = node.prev;
		node.prev.next = node.next;
		if (head == node)
		{
			head = node.next;
		}
	}
	node.Invalidate();
	count--;
	version++;
}

四、Find和FindLast方法

直接看代码，时间复杂度为O(n)

public LinkedListNode<T> Find(T value)
{
	LinkedListNode<T> node = head;
	EqualityComparer<T> c = EqualityComparer<T>.Default;
	if (node != null)
	{
		if (value != null)
		{
			do
			{
				if (c.Equals(node.item, value))
				{
					return node;
				}
				node = node.next;
			} while (node != head);
		}
		else
		{
			do
			{
				if (node.item == null)
				{
					return node;
				}
				node = node.next;
			} while (node != head);
		}
	}
	return null;
}

public LinkedListNode<T> FindLast(T value)
{
	if (head == null) return null;

	LinkedListNode<T> last = head.prev;
	LinkedListNode<T> node = last;
	EqualityComparer<T> c = EqualityComparer<T>.Default;
	if (node != null)
	{
		if (value != null)
		{
			do
			{
				if (c.Equals(node.item, value))
				{
					return node;
				}

				node = node.prev;
			} while (node != last);
		}
		else
		{
			do
			{
				if (node.item == null)
				{
					return node;
				}
				node = node.prev;
			} while (node != last);
		}
	}
	return null;
}

五、序列化与反序列化

如何将链表序列化为数组，.net framework提供了GetObjectData和OnDeserialization

//该序列化是将链表数据结构转换为数组保存
//序列化后的头两个int长度链表的version和结点个数
[SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
{
	if (info == null)
	{
		throw new ArgumentNullException("info");
	}
	info.AddValue(VersionName, version);
	info.AddValue(CountName, count); 
	if (count != 0)
	{
		T[] array = new T[Count];
		CopyTo(array, 0);
		info.AddValue(ValuesName, array, typeof(T[]));
	}
}

public virtual void OnDeserialization(Object sender)
{
	if (siInfo == null)
	{
		return;  
	}

	int realVersion = siInfo.GetInt32(VersionName);
	int count = siInfo.GetInt32(CountName);

	if (count != 0)
	{
		T[] array = (T[])siInfo.GetValue(ValuesName, typeof(T[]));

		if (array == null)
		{
			throw new SerializationException(SR.GetString(SR.Serialization_MissingValues));
		}
		for (int i = 0; i < array.Length; i++)
		{
			AddLast(array[i]);
		}
	}
	else
	{
		head = null;
	}

	version = realVersion;
	siInfo = null;
}