双向链表图解
程序实现
下面的实现中没有使用头节点（即头节点就是首节点）
Node类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test
{
class Node<T>
{
T data; //数据域
Node<T> next; //后继节点
Node<T> pre; //前驱节点
internal Node<T> Next { get => next; set => next = value; }
internal Node<T> Pre { get => pre; set => pre = value; }
public T Data { get => data; set => data = value; }
//构造器
public Node(T value, Node<T> next, Node<T> pre)
{
Data = value;
Next = next;
Pre = pre;
}
//构造器
public Node(T value)
{
Data = value;
}
//构造器
public Node(Node<T> next,Node<T> pre)
{
Next = next;
Pre = pre;
}
//构造器
public Node(Node<T> next)
{
Next = next;
}
//构造器
public Node()
{
Data = default(T);
Next = null;
Pre = null;
}
}
}
DoubleList类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test
{
class DoubleList<T>
{
Node<T> head; //头节点
internal Node<T> Head { get => head; set => head = value; }
//构造器
public DoubleList() { Head = null; }
/// <summary>
/// 链表判空
/// </summary>
/// <returns>为空返回true</returns>
public bool IsEmpty() { return Head == null; }
/// <summary>
/// 取链表长度
/// </summary>
/// <returns>链表长度</returns>
public int GetLenth()
{
//链表为空
if (IsEmpty()) { return 0; }
//只有一个元素
if (Head.Next == null) { return 1; }
//遍历链表
Node<T> c = Head;
int i = 1;
while (c.Next != null)
{
c = c.Next;
++i;
}
return i;
}
/// <summary>
/// 在末尾添加新元素
/// </summary>
public void Append(T value)
{
Node<T> item = new Node<T>(value);
//链表为空时，直接覆盖首节点
if (IsEmpty()) { Head = item; return; }
//只有一个元素时，直接挂载
if (Head.Next == null)
{
Head.Next = item;
item.Pre = Head;
return;
}
//遍历至末尾添加
Node<T> c = Head;
while (c.Next != null) { c = c.Next; }
c.Next = item;
item.Pre = c;
}
/// <summary>
/// 在指定位置后插入元素
/// </summary>
/// <param name="value">元素值</param>
/// <param name="i">元素位置</param>
public void Insert(T value, int i)
{
//插入位置大于链表总长度
if (GetLenth() < i)
{
Console.WriteLine("插入位置不正确");
return;
}
Node<T> c = new Node<T>(value);//新节点
//插入到头节点位置
if (i == 1)
{
Head.Next.Pre = c; //头节点的后继节点的前驱指向新节点
c.Next = Head.Next; //新节点的后继指向头节点的后继节点
c.Pre = Head; //新节点的前驱指向头节点
Head.Next = c; //头节点的后继指向新节点
return;
}
//遍历插入
int j = 1;
Node<T> cur = Head;
while (cur.Next != null && i > j)
{
cur = cur.Next;
++j;
}
if (j == i)
{
cur.Next.Pre = c; //当前节点的后继节点的前驱指向新节点
c.Next = cur.Next; //新节点的后继指向当前节点
c.Pre = cur; //新节点的前驱指向当前节点
cur.Next = c; //当前节点的后继指向新节点
}
else
{
Console.WriteLine("位置错误");
}
}
/// <summary>
/// 删除指定位置的元素
/// </summary>
/// <param name="i"></param>
public void Delete(int i)
{
if (GetLenth() < i)
{
Console.WriteLine("位置不正确");
return;
}
//删除首节点
if (i == 1)
{
Head = Head.Next;
Head.Pre = null;
return;
}
//遍历删除
Node<T> c = Head;
int j = 1;
while (c.Next != null && j < i)
{
c = c.Next;
++j;
}
if (j == i)
{
//如果是最后一个节点，直接将其前驱节点的后继节点置为空，将其前驱节点置为空
if (c.Next == null)
{
c.Pre.Next = null;
c.Pre = null;
}
else
{
c.Next.Pre = c.Pre;
c.Pre.Next = c.Next;
}
}
else {
Console.WriteLine("位置错误");
}
}
/// <summary>
/// 根据位置获取元素值
/// </summary>
/// <param name="i">元素位置</param>
/// <returns>元素值</returns>
public T GetElem(int i)
{
if (GetLenth() < i)
{
Console.WriteLine("位置不正确");
return default(T);
}
if (i == 1)
{
return Head.Data;
}
Node<T> c = Head;
int j = 1;
while (c.Next != null && j < i)
{
c = c.Next;
++j;
}
if (i == j)
{
return c.Data;
}
else
{
Console.WriteLine("位置错误");
return default(T);
}
}
/// <summary>
/// 根据元素值，获取元素位置
/// </summary>
/// <param name="data"></param>
/// <returns></returns>
public int GetPos(T data)
{
if (IsEmpty())
{
Console.WriteLine("链表为空");
return -1;
}
if (Head.Data.Equals(data))
{
return 1;
}
Node<T> c = Head;
int i = 1;
int length = GetLenth();
while (c != null && !c.Data.Equals(data) && i <= length)
{
c = c.Next;
++i;
}
if (i <= length)
return i;
else
return -1;
}
}
}
Program类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test
{
class Program
{
static void Main(string[] args)
{
DoubleList<string> link = new DoubleList<string>();
link.Append("123");
link.Append("456");
link.Append("789");
//link.Insert("qwe", 1);
//link.Insert("asd", 2);
//link.Delete(2);
//Console.WriteLine(link.GetElem(1));
Console.WriteLine(link.GetPos("789"));
Node<string> c = link.Head;
Console.WriteLine("---正序输出");
while (c.Next!=null) {
Console.WriteLine(c.Data);
c = c.Next;
}
Console.WriteLine(c.Data);
Console.WriteLine("---逆序输出");
while (c != null)
{
Console.WriteLine(c.Data);
c = c.Pre;
}
Console.WriteLine("---长度");
Console.WriteLine(link.GetLenth());
}
}
}
