双向链表
基本上,我们可以认为双向链表是单链表的一个改进。这个改进一个有益的地方就是,双链表不必像单链表一样,为了查找一个元素,沿着链表的特定一个方向,从头遍历到尾。通过双链表,我们可以沿着正反两个方向对链表内的元素进行查找。
双链表的结点与单链表(循环链表)的稍稍有点不同,主要的不同就在与,双链表的节点多出了一个连接前一个节点的字段(详见灰色部分)。如下所示
class DulNode T
{
private T data;
/// summary
/// 数据域
/// /summary
public T Data
{
get {return data;}
set { data = value;}
}
private DulNode T next;
/// summary
/// 引用域
/// /summary
public DulNode T Next
{
get {return next;}
set { next = value;}
}
private DulNode T prior;
public DulNode T Prior
{
get {return prior;}
set { prior = value;}
}
//头结点构造函数
public DulNode(DulNode T next)
:this(default(T),null, next)
{
}
//头结点构造函数
public DulNode(T data)
:this(data,null,null)
{
}
//普通结点构造函数
public DulNode(T data,DulNode T prior, DulNode T next)
{
this.Data = data;
this.Next = next;
this.Prior = prior;
}
/// summary
/// 空构造函数
/// /summary
public DulNode()
:this(default(T),null,null)
{
}
//尾结点构造函数
public DulNode(T data,DulNode T prior)
:this(data, prior,null)
{
}
}
我们初始化一个双向链表,以便让大家更加直观的了解到双向链表中头结点和尾节点的不同。这个链表有四个节点,我们分别用0,1,2,3填充这个链表。
头节点如下所示:(其中next代表连接后一个节点的后导节点,prior代表连接前一个节点的前导节点)
尾节点如下所示:
普通的节点如下所示:
双向链表具体的实现如下所示
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
class DulList T : IListDS T
{
class DulNode T
{
private T data;
/// summary
/// 数据域
/// /summary
public T Data
{
get {return data;}
set { data = value;}
}
private DulNode T next;
/// summary
/// 引用域
/// /summary
public DulNode T Next
{
get {return next;}
set { next = value;}
}
private DulNode T prior;
public DulNode T Prior
{
get {return prior;}
set { prior = value;}
}
//头结点构造函数
public DulNode(DulNode T next)
:this(default(T),null, next)
{
}
//头结点构造函数
public DulNode(T data)
:this(data,null,null)
{
}
//普通结点构造函数
public DulNode(T data, DulNode T prior, DulNode T next)
{
this.Data = data;
this.Next = next;
this.Prior = prior;
}
/// summary
/// 空构造函数
/// /summary
public DulNode()
:this(default(T),null,null)
{
}
//尾结点构造函数
public DulNode(T data, DulNode T prior)
:this(data, prior,null)
{
}
}
private DulNode T Head;
public DulList(T[] t)
{
this.Head =new DulNode T (t[0]);
DulNode T Current;
Current = Head;
for(int i =1; i t.Length; i++)
{
DulNode T newNode =new DulNode T (t[i]);
//设置前一个连接点
newNode.Prior = Current;
//当前节点的next设置为新的节点
Current.Next = newNode;
//将当前节点的引用域指向新的节点
Current = newNode;
}
}
public DulList()
{
}
publicint Lenth
{
get {returnthis.GetLength();}
}
public States Append(T item)
{
//(1)头结点没有
if(Head ==null)
{
Head =new DulNode T (item);
return States.Success;
}
//(2)正常的插入情况
DulNode T Last;
Last = Head;
//遍历到最后一个结点,在最后一个结点附加上
while(null!= Last.Next)
{
Last = Last.Next;
}
DulNode T newNode =new DulNode T (item);
Last.Next = newNode;
newNode.Prior = Last;
return States.Success;
}
publicvoid Clear()
{
Head =null;
}
public T Delete(int index,out States states)
{
bool isIndexTrue = index 0|| index =this.GetLength();
if(IsEmpty()==true|| isIndexTrue)
{
states = States.Fail;
returndefault(T);
}
//找到指定的结点
DulNode T Current = Head;
DulNode T Previous = Head;
int Count =0;
while(Count != index Current.Next !=null)
{
Previous = Current;
Current = Current.Next;
Count++;
}
T ValueToDel = Current.Data;
//是否是头结点
if(Count ==0)
{
Head = Current.Next;
Current.Next.Prior =null;
}
//是否是普通的结点
if(Count !=0 Current.Next !=null)
{
Previous.Next = Current.Next;
Current.Next.Prior = Previous;
}
//是否是最后一个结点
if(Count !=0 Current.Next ==null)
{
Previous.Next =null;
}
//删除结点
states = States.Success;
return ValueToDel;
}
public T GetElem(int i)
{
if(i 0|| i =this.GetLength())
{
returndefault(T);
}
if(IsEmpty()==true)
{
returndefault(T);
}
DulNode T Last = Head;
int Count =0;
while(Count != i Last.Next !=null)
{
Last = Last.Next;
Count++;
}
return Last.Data;
}
publicint GetLength()
{
if(Head ==null)
{
return0;
}
DulNode T Last;
Last = Head;
int Count =0;
while(Last.Next !=null)
{
Last = Last.Next;
Count++;
}
return++Count;
}
public States Insert(T item,int index)
{
bool isIndexTrue = index 0|| index this.GetLength();
if(isIndexTrue)
{
return States.Fail;
}
//如果链表为空
if(IsEmpty()==true)
{
Head.Data = item;
}
//如果是第一个结点
if(index ==0)
{
DulNode T NewNode =new DulNode T (item);
NewNode.Next = Head;
Head.Prior = NewNode;
Head = NewNode;
return States.Success;
}
//如果是普通的结点
DulNode T Previous = Head;//当前节点的前一个
int Count =0;
while(Count != index -1 Previous.Next !=null)//因为要取到插入位置的前一个节点所以用Count != index-1的判断
{
Previous = Previous.Next;
Count++;
}
//如果是最后一个结点
if(this.GetLength()== index)
{
DulNode T NewNode =new DulNode T (item);
Previous.Next = NewNode;
NewNode.Prior = Previous;
return States.Success;
}
if(Count == index -1)
{
DulNode T NewNode =new DulNode T (item);
DulNode T Current = Previous.Next;
NewNode.Next = Current;
Current.Prior = NewNode;
NewNode.Prior = Previous;
Previous.Next = NewNode;
}
return States.Success;
}
publicbool IsEmpty()
{
return Head ==null?true:false;
}
publicint Locate(T value,out States states)
{
if(IsEmpty()==true)
{
states = States.Fail;
return0;
}
DulNode T Last = Head;
int Index =0;
while(Last.Next !=null (!value.Equals(Last.Data)))
{
Last = Last.Next;
Index++;
}
states = States.Success;
return Index;
}
}
}
作者:kissazi2
出处:http://www.cnblogs.com/kissazi2/
本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载:http://www.cnblogs.com/kissazi2/p/3193965.html
链表——初识链表 链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只管的表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
相关文章
- 链表题目汇总
- 双向链表操作
- 双向链表
- (剑指Offer)面试题27:二叉搜索树与双向链表
- [数据结构] 数组与链表的优缺点和区别
- 双向链表排序
- 【LeetCode 24】两两交换链表中的节点
- 【数据结构笔记11】数据结构之二叉树的存储结构(顺序存储、二叉链表、三叉链表)
- 445. 两数相加 II-原地算法-链表处理
- 面试题 02.07.返回 链表相交节点
- 双向循环链表修复
- 简单易懂的C语言实现双向链表代码
- leetcode 19. 删除链表的倒数第 N 个结点 js实现
- 链表:反转链表
- 单链表 链表翻转
- 力扣:160. 相交链表
- 力扣:21. 合并两个有序链表
- LeetCode 430. 扁平化多级双向链表
- 链表的插入实现
- 【21】合并两个有序链表 【LeetCode】
- 【数据结构与算法】什么是双向链表?并用代码手动实现一个双向链表
- 数据结构1-1 链表
- 【数据结构】从零开始逐步实现带哨兵位循环双向链表 | 学会用 “思路草图“ 将思路转变成代码