数据结构-双向链表&双向循环链表
分类:
IT文章
•
2023-12-06 13:13:43
借图:http://www.cnblogs.com/skywang12345/p/3561803.html#a33
双向链表
双向链表(双链表)是链表的一种。和单链表一样,双链表也是由节点组成,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。
实现:接口
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _001_线性表
{
interface IListDS<T>
{
int GetLength();
void Clear();
bool IsEmpty();
void Add(T item);
void Insert(T item, int index);
T Delete(int index);
T this[int index] { get; }
T GetEle(int index);
int Locate(T value);
}
}
View Code
双向节点:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace _001_线性表
{
/// <summary>
/// 双向节点
/// </summary>
/// <typeparam name="T"></typeparam>
class DbNode<T>
{
private T data;
private DbNode<T> prev;
private DbNode<T> next;
public DbNode(T val,DbNode<T> p,DbNode<T> n)
{
this.data = val;
this.prev = p;
this.next = n;
}
public DbNode(DbNode<T> p)
{
next = p;
}
public DbNode(T val)
{
data = val;
next = null;
prev = null;
}
public DbNode()
{
data = default(T);
next = null;
prev = null;
}
public T Data
{
get { return data; }
set { data = value; }
}
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
public void SetNode(DbNode<T> pre,DbNode<T> next)
{
this.prev = pre;
this.next = next;
}
}
}
View Code
双向链表:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace _001_线性表
{
/// <summary>
/// 双向链表
/// </summary>
/// <typeparam name="T"></typeparam>
class DoubleLink<T>:IListDS<T>
{
#region IListDS<T> 成员
private DbNode<T> _linkHead;
public DoubleLink()
{
_linkHead = null;
}
public int GetLength()
{
if (IsEmpty()) return 0;
DbNode<T> temp = _linkHead;
int length = 1;
while (temp.Next != null)
{
length++;
temp = temp.Next;
}
return length;
}
public void Clear()
{
_linkHead = null;
}
public bool IsEmpty()
{
return _linkHead == null;
}
/// <summary>
/// 在双向链表的尾端添加一个新数据
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
DbNode<T> newNode = new DbNode<T>(item);
if (IsEmpty())
{
_linkHead = newNode;
}
else
{
DbNode<T> preNode = GetListItem(this.GetLength() - 1);
newNode.Prev = newNode;
preNode.Next = newNode.Prev;
newNode.Prev = preNode;
}
}
/// <summary>
/// 获取指定位置的双向链表项目,头项从0开始
/// </summary>
public DbNode<T> GetListItem(int index)
{
if (index < 0)
throw new Exception("索引不能小于0");
if (index > this.GetLength() - 1)
throw new Exception("索引超出列表总长度");
DbNode<T> temp = _linkHead;
for (int i = 0; i < index; i++)
{
temp = temp.Next;
}
return temp;
}
/// <summary>
/// 在双向链表指定的位置插入一个新项
/// </summary>
public void Insert(T item, int index)
{
if (index < 0)
throw new Exception("插入位置不能小于0");
if (index > this.GetLength() + 1)
throw new Exception("插入位置超出链表长度");
DbNode<T> newNode = new DbNode<T>(item);
if (index == 0)
{
newNode.Next = _linkHead;
_linkHead = newNode;
}
else
{
DbNode<T> preNode = GetListItem(index - 1); //要插入位置前面的节点
DbNode<T> atfNode = GetListItem(index);//要插入位置后面的节点
preNode.Next = new DbNode<T>(item, preNode, atfNode);
}
}
/// <summary>
/// 删除指定位置的双向链表项
/// </summary>
/// <param name="index"></param>
public T Delete(int index)
{
if (index < 0)
throw new Exception("删除位置不能小于0");
if (index > this.GetLength() - 1)
throw new Exception("插入位置超出链表长度");
T data = default(T);
if (index == 0)
{
data = _linkHead.Data;
_linkHead = _linkHead.Next;
if(!IsEmpty())
this._linkHead.Prev = null;
}
else
{
DbNode<T> DelNode = GetListItem(index); //取到要删除的节点
data = DelNode.Data;
DbNode<T> preNode = DelNode.Prev;
DbNode<T> nextNode = DelNode.Next;
preNode.Next = nextNode;
nextNode.Prev = preNode;
}
return data;
}
public T this[int index]
{
get { return GetEle(index); }
}
public T GetEle(int index)
{
DbNode<T> temp = _linkHead;
for (int i = 0; i < index; i++)
{
temp = temp.Next;
}
return temp.Data;
}
public int Locate(T value)
{
DbNode<T> temp = _linkHead;
if (IsEmpty())
{
return -1;
}
else
{
int index = 0;
while (true)
{
if (!temp.Data.Equals(value))
{
if (temp.Next != null)
{
index++;
temp = temp.Next;
}
else
{
break;
}
}
else
{
return index;
}
}
return -1;
}
}
#endregion
}
}
双向循环链表
从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双链表的示意图如下:
表头为空,表头的后继节点为"节点10"(数据为10的节点);"节点10"的后继节点是"节点20"(数据为10的节点),"节点20"的前继节点是"节点10";"节点20"的后继节点是"节点30","节点30"的前继节点是"节点20";...;末尾节点的后继节点是表头。
双链表删除节点
删除"节点30"
删除之前:"节点20"的后继节点为"节点30","节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40","节点40" 的前继节点为"节点30"。
删除之后:"节点20"的后继节点为"节点40","节点40" 的前继节点为"节点20"。
双链表添加节点
在"节点10"与"节点20"之间添加"节点15"
添加之前:"节点10"的后继节点为"节点20","节点20" 的前继节点为"节点10"。
添加之后:"节点10"的后继节点为"节点15","节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20","节点20" 的前继节点为"节点15"。
实现:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _001_线性表
{
/// <summary>
/// 双向循环链表
/// </summary>
/// <typeparam name="T"></typeparam>
class DoubleLoopLink<T> : IListDS<T>
{
private DbNode<T> _linkHead;
public T this[int index] =>GetEle(index);
public void Add(T item)
{
DbNode<T> newNode = new DbNode<T>(item, null, null);
if (IsEmpty())
{
_linkHead = newNode;
_linkHead.Prev = _linkHead;
_linkHead.Next = _linkHead;
}
else
{
DbNode<T> preNode = _linkHead;
while (preNode.Next != _linkHead)
{
preNode = preNode.Next;
}
preNode.Next = newNode;//链表的尾部 的后指针 指向新的节点
newNode.SetNode(preNode, _linkHead);
_linkHead.Prev = newNode; //头部的 前指针 指向 新的尾部
}
}
public void Clear()
{
_linkHead = null;
}
public T Delete(int index)
{
T data = default(T);
if (IsEmpty())
throw new Exception("链表为空,没有可清除的项");
if (index < 0 || index > this.GetLength() - 1)
throw new Exception("给定索引超出链表长度");
DbNode<T> preNode = _linkHead;
if (index == 0)
{
while (preNode.Next != _linkHead)
{
preNode = preNode.Next;
}
this._linkHead = _linkHead.Next;
this._linkHead.Prev = preNode;
data = preNode.Next.Data;
preNode.Next = this._linkHead;
}
else
{
for (int i = 1; i < index - 1; i++)
{
preNode = preNode.Next;
}
//看图比较好理解
DbNode<T> aftNode = preNode.Next.Next; //要删除的节点 后面的节点
preNode.Next = aftNode;//要删除节点的前面节点 的后指针 指向 要删除的节点 后面的节点
aftNode.Prev = preNode; //要删除的节点 前面的节点 指向 要删除节点的前面节点
}
return data;
}
public T GetEle(int index)
{
DbNode<T> temp = _linkHead;
for (int i = 0; i < index; i++)
{
temp = temp.Next;
}
return temp.Data;
}
public int GetLength()
{
if (IsEmpty()) return 0;
DbNode<T> temp = _linkHead;
int length = 1;
while (temp.Next != _linkHead)
{
length++;
temp = temp.Next;
}
return length;
}
/// <summary>
/// 插入
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
if (IsEmpty())
throw new Exception("数据链表为空");
if (index < 0 || index > this.GetLength())
throw new Exception("给定索引超出链表长度");
DbNode<T> newNode = new DbNode<T>(item);
DbNode<T> preNode = _linkHead;
if (index == 0) //等于零 先找到 链表中 head的前一个节点 这个节点连接 head
{
while (preNode.Next != _linkHead)
{
preNode = preNode.Next;
}
preNode.Next = newNode;
newNode.SetNode(preNode, _linkHead);
_linkHead.Prev = newNode;
return;
}
else
{
for (int i = 1; i < index - 1; i++)
{
preNode = preNode.Next;
}
//preNode要插入位置的前节点
DbNode<T> atfNode = preNode.Next;//要插入节点的后节点
preNode.Next = newNode; //后指针 连上新节点
newNode.SetNode(preNode,atfNode);
atfNode.Prev = newNode;//要插入节点的后节点 连上 新节点
}
}
public bool IsEmpty()
{
return _linkHead == null;
}
public int Locate(T value)
{
if (IsEmpty())
throw new Exception("链表为空");
DbNode<T> preNode = _linkHead;
int index = 0;
while (true)
{
if (!preNode.Data.Equals(value))
{
if (preNode.Next != _linkHead)
{
index++;
preNode = preNode.Next;
}
else
{
break;
}
}
else
{
return index;
}
}
return -1;
}
}
}
View Code