XIAOSUO 记录个人学习的足迹

一、双向链表的表示

　　双链表是结点有两个引用域的链表：一个指向直接后继结点，一个指向直接前驱结点。这种类型定义如下：

public class DNode<T>
{
	private T data;
	private DNode<T> prev;
	private DNode<T> next;

	public DNode(T data, DNode<T> next)
	{
		this.data = data;
		this.next = next;
	}

	public DNode(T data)
	{
		this.data = data;
		this.next = null;
	}

	public DNode(DNode<T> next)
	{
		this.next = next;
	}

	public DNode()
	{
		this.data = default(T);
		this.next = null;
	}

	public T Data
	{
		get { return this.data; }
		set { this.data = value; }
	}

	public DNode<T> Next
	{
		get { return this.next; }
		set { this.next = value; }
	}

	public DNode<T> Prev
	{
		get { return this.prev; }
		set { this.prev = value; }
	}
}

二、双向链表的实现

　　在双链表中，有些操作(如取元素、定位等)算法中仅涉及后继结点，此时双向链表的算法和单链表的算法均相同，但对插入、删除操作，双向链表需同时修改后继和前驱两个引用，比单链表要复杂一些，其操作如下：

public class DLinkList<T>
{
	private DNode<T> start;
	private int length;

	public DLinkList()
	{
		start = null;
	}

	public int Length
	{
		get { return this.length; }
	}

	public void InsertNode(T data)
	{
		if (start == null)
		{
			start = new DNode<T>(data);
			length = 1;
			return;
		}

		DNode<T> current = start;
		while (current.Next != null)
		{
			current = current.Next;
		}

		DNode<T> newData = new DNode<T>(data);
		current.Next = newData;
		newData.Prev = current;
		length++;
	}

	public void InsertNode(T data, int i)
	{
		if (i < 1 || i > length + 1)
		{
			throw new Exception("插入的位置错误");
		}

		DNode<T> current;
		DNode<T> previous;
		DNode<T> newNode = new DNode<T>(data);

		if (i == 1)
		{
			newNode.Next = start;
			start.Prev = newNode;
			start = newNode;
			length++;
			return;
		}

		current = start;
		previous = null;
		int j =1;
		while (current != null && j < i)
		{
			previous = current;
			current = current.Next;
			j++;
		}

		newNode.Next = current;
		newNode.Prev = previous;
		if (current != null)
		{
			current.Prev = newNode;
		}
		previous.Next = newNode;
		length++;
	}

	public void DeleteNode(int i)
	{
		if (IsEmpty() || i < 1 || i > length)
		{
			throw new Exception("链表为空或要删除的位置错误");
		}

		DNode<T> current = start;

		if (i == 1)
		{
			start = current.Next;
			start.Prev = null;
			length--;
			return;
		}

		DNode<T> previous = null;
		int j = 1;
		while (current.Next != null && j < i)
		{
			previous = current;
			current = current.Next;
			j++;
		}

		previous.Next = current.Next;
		if (current.Next != null)
		{
			current.Next.Prev = previous;
		}
		current = null;
		length--;
	}

	public T SearchNode(int i)
	{
		if (IsEmpty() || i < 1 || i > length)
		{
			throw new Exception("链表为空或者要查找的位置不正确");
		}

		DNode<T> current = start;
		int j = 1;

		while (current.Next != null && j < i)
		{
			current = current.Next;
			j++;
		}
		return current.Data;
	}

	public T SearchNode(T value)
	{
		if (IsEmpty())
		{
			throw new Exception("链表为空");
		}

		DNode<T> current = start;
		int i = 1;

		while (current.Data.ToString().Contains(value.ToString()) && current != null)
		{
			current = current.Next;
			i++;
		}
		if (current != null)
			return current.Data;
		else
			return default(T);
	}

	public void Clear()
	{
		start = null;
		length = 0;
	}

	public bool IsEmpty()
	{
		if (start == null)
			return true;
		else
			return false;
	}
}