双向链表的实现

发表评论
8,157 views

A+

所属分类：Fly数据结构与算法原创文章

从双向链表这个名字

就可以知道很多了

普通的单链表，只能往这一个方向进行查找遍历

而双向链表，他可以从两个方向进行查找

只要知道了某个结点，就可以知道它的前驱和后继

下面实现一下

class DoubleLink<T>
{
    class Node {
        public T data;
        public Node pre;
        public Node next;
    }

    private Node _head;
    private Node _last;
    private int _currentLength = 0;

class DoubleLink<T>

{

class Node {

public T data;

public Node pre;

public Node next;

}

private Node _head;

private Node _last;

private int _currentLength = 0;

这里定义一个抽象的数据类

用于保存数据，前驱，后继

声明一个指向头结点的引用

声明一个指向尾结点的引用

定义一个int变量用于保存链表的长度

//初始化为只有头结点的空链表
public DoubleLink() {
    _head = new Node();
    _head.pre = null;
    _head.next = null;

    _last = _head;
}

//初始化为只有头结点的空链表

public DoubleLink() {

_head = new Node();

_head.pre = null;

_head.next = null;

_last = _head;

}

初始化链表为空链表

新建头结点

前驱和后继都为null

初始化尾结点也为头结点

//添加元素在尾部
public bool Add(T element) {
    Node addNode = new Node();
    addNode.data = element;
    addNode.pre = this._last;
    addNode.next = null;
    this._last.next = addNode;
    this._last = addNode;

    this._currentLength++;
    return true;
}

//添加元素在尾部

public bool Add(T element) {

Node addNode = new Node();

addNode.data = element;

addNode.pre = this._last;

addNode.next = null;

this._last.next = addNode;

this._last = addNode;

this._currentLength++;

return true;

}

注意的是双向链表

所以要设置它们的前驱和后继

这里只是在尾部添加，所以新加结点后面不会有结点

这里就只需要修改与原尾结点的联系

//在头部添加元素
public bool AddAtFirst(T element) {
    Node addNode = new Node();
    addNode.data = element;
    addNode.pre = this._head;
    addNode.next = this._head.next;

    if (this._head.next != null)
    {
        this._head.next.pre = addNode;
        this._head.next = addNode;
    }
    else {
        //为空链表
        this._last = addNode;
    }

    this._currentLength++;
    return true;
}

//在头部添加元素

public bool AddAtFirst(T element) {

Node addNode = new Node();

addNode.data = element;

addNode.pre = this._head;

addNode.next = this._head.next;

if (this._head.next != null)

{

this._head.next.pre = addNode;

this._head.next = addNode;

}

else {

//为空链表

this._last = addNode;

}

this._currentLength++;

return true;

}

这里又不同于在尾部添加结点

这里在头部添加

则表示新加的结点的前面有头结点

后面有链表的第一个结点（除了空链表的情况下）

需要设置的不单单是新加的结点

还需要设置它前驱的后继

设置它后继的前驱

都还是它

（绕傻你^_^）

//获取某个位置的结点
private Node GetNodeByIndex(int index) {
    if (index < 0 || index > this._currentLength) {
        Console.WriteLine("索引错误！");
        return null;
    }

    int i;
    Node goNode;

    if (index < this._currentLength / 2 + 1)
    {
        //想获得的结点靠前，通过前序向后遍历
        i = 0;
        goNode = this._head;
        while (i != index && goNode.next != null)
        {
            goNode = goNode.next;
            i++;
        }
                
    }
    else
    {
        //后序向前遍历寻找结点
        i = this._currentLength;
        goNode = this._last;

        while (i != index && goNode.pre != null) {
            goNode = goNode.pre;
            i--;
        }
    }

    return goNode;
}

//获取某个位置的结点

private Node GetNodeByIndex(int index) {

if (index < 0 || index > this._currentLength) {

Console.WriteLine("索引错误！");

return null;

}

int i;

Node goNode;

if (index < this._currentLength / 2 + 1)

{

//想获得的结点靠前，通过前序向后遍历

i = 0;

goNode = this._head;

while (i != index && goNode.next != null)

{

goNode = goNode.next;

i++;

}

else

{

//后序向前遍历寻找结点

i = this._currentLength;

goNode = this._last;

while (i != index && goNode.pre != null) {

goNode = goNode.pre;

i--;

}

return goNode;

}

这个重点说说吧

前面那些都可以参考单链表，并没有什么不同

双向链表既然可以有两个方向可以查找元素

当然是哪边近就要从哪边查找啦

所以

①还是要判断一下索引的合法性

②判断一下是那一边离index近，如果是左边就用前面遍历

如果是右边就用后面遍历

③遍历到第index个结点（自己理解或看单链表）

④返回这个节点

0返回的是头结点

//获取某个位置的值
public bool GetElement(int index, ref T element) {
    //排除头结点
    if (index == 0) {
        Console.WriteLine("头结点没有数据!");
        return false;
    }

    Node node = this.GetNodeByIndex(index);

    if (node == null) {
        return false;
    }

    element = node.data;
    return true;
}

//获取某个位置的值

public bool GetElement(int index, ref T element) {

//排除头结点

if (index == 0) {

Console.WriteLine("头结点没有数据!");

return false;

}

Node node = this.GetNodeByIndex(index);

if (node == null) {

return false;

}

element = node.data;

return true;

}

不说了！！！

//插入结点
public bool Inset(int index, T element) {
    Node preNode = this.GetNodeByIndex(index - 1);
    if (preNode == null || preNode.next == null) {
        return false;
    }

    Node addNode = new Node();
    addNode.data = element;
    addNode.pre = preNode;
    addNode.next = preNode.next;

    preNode.next.pre = addNode;
    preNode.next = addNode;

    this._currentLength++;
    return true;
}

//插入结点

public bool Inset(int index, T element) {

Node preNode = this.GetNodeByIndex(index - 1);

if (preNode == null || preNode.next == null) {

return false;

}

Node addNode = new Node();

addNode.data = element;

addNode.pre = preNode;

addNode.next = preNode.next;

preNode.next.pre = addNode;

preNode.next = addNode;

this._currentLength++;

return true;

}

插入结点

需要设置新加结点的前驱为被插结点的前驱

新加结点的后继为被插结点

设置被插结点的前驱为新加结点

设置被插结点前驱的后继为新加结点

总共关系要设置4个

注意好顺序，别把结点改乱了

//删除某个位置的结点
public bool Delete(int index, ref T element) {
    Node preNode = this.GetNodeByIndex(index - 1);

    if (preNode == null || preNode.next == null) {
        Console.WriteLine("删除的元素不存在！");
        return false;
    }

    Node deleteNode = preNode.next;
    element = deleteNode.data;

    if (index == this._currentLength)
    {
        this._last = preNode;
    }
    else {
        deleteNode.next.pre = preNode;
    }
            
    preNode.next = deleteNode.next;
    deleteNode = null;

            

    this._currentLength--;
    return true;
}

//删除某个位置的结点

public bool Delete(int index, ref T element) {

Node preNode = this.GetNodeByIndex(index - 1);

if (preNode == null || preNode.next == null) {

Console.WriteLine("删除的元素不存在！");

return false;

}

Node deleteNode = preNode.next;

element = deleteNode.data;

if (index == this._currentLength)

{

this._last = preNode;

}

else {

deleteNode.next.pre = preNode;

}

preNode.next = deleteNode.next;

deleteNode = null;

this._currentLength--;

return true;

}

这里注意的就是如果要删除的是最后一个结点的话

是不需要设置被删结点的后继的前驱的

因为它都没有后继

尾结点被删除后，那么上一个结点就是尾结点了

测试

static void TestDoubleLink() {

    //添加测试
    DoubleLink<int> d = new DoubleLink<int>();
    d.Add(2);
    d.Add(90);
    d.AddAtFirst(32);
    d.Add(8);
    PrintDoubleLink(d,"添加四个元素后");
    Console.WriteLine();

    //插入测试
    PrintDoubleLink(d, "插入前：");
    d.Inset(1, 88);
    PrintDoubleLink(d, "一号位插入88后：");
    d.Inset(5, 60);
    PrintDoubleLink(d, "五号位插入60后：");
    d.AddAtFirst(99);
    PrintDoubleLink(d, "在头部添加99后：");
    Console.WriteLine();

    //删除测试
    int data = 0;
    PrintDoubleLink(d, "删除元素前：");
    d.Delete(4, ref data);
    PrintDoubleLink(d, "删除第四个元素后：");
    d.Delete(1, ref data);
    d.Delete(1, ref data);
    d.Delete(1, ref data);
    d.Delete(1, ref data);
    d.Delete(1, ref data);
    d.Delete(1, ref data);
    d.Delete(1, ref data);
    PrintDoubleLink(d, "删除完元素后：");
    d.Add(30);
    d.AddAtFirst(20);
    PrintDoubleLink(d, "在添加两个元素后：");
    Console.WriteLine();

    //索引测试
    d.Delete(30, ref data);
    d.Inset(0, 1);
    d.GetElement(0 ,ref data);
    d.GetElement(-1, ref data);
}


static void PrintDoubleLink(DoubleLink<int> d, string text = "输出：")
{
    int data = 0;

    Console.Write(text);
    for (int i = 0; i < d.GetLength(); i++)
    {
        d.GetElement(i + 1, ref data);
        Console.Write(data.ToString() + " ");
    }
    Console.WriteLine();
}

static void TestDoubleLink() {

//添加测试

DoubleLink<int> d = new DoubleLink<int>();

d.Add(2);

d.Add(90);

d.AddAtFirst(32);

d.Add(8);

PrintDoubleLink(d,"添加四个元素后");

Console.WriteLine();

//插入测试

PrintDoubleLink(d, "插入前：");

d.Inset(1, 88);

PrintDoubleLink(d, "一号位插入88后：");

d.Inset(5, 60);

PrintDoubleLink(d, "五号位插入60后：");

d.AddAtFirst(99);

PrintDoubleLink(d, "在头部添加99后：");

Console.WriteLine();

//删除测试

int data = 0;

PrintDoubleLink(d, "删除元素前：");

d.Delete(4, ref data);

PrintDoubleLink(d, "删除第四个元素后：");

d.Delete(1, ref data);

PrintDoubleLink(d, "删除完元素后：");

d.Add(30);

d.AddAtFirst(20);

PrintDoubleLink(d, "在添加两个元素后：");

Console.WriteLine();

//索引测试

d.Delete(30, ref data);

d.Inset(0, 1);

d.GetElement(0 ,ref data);

d.GetElement(-1, ref data);

}

static void PrintDoubleLink(DoubleLink<int> d, string text = "输出：")

{

int data = 0;

Console.Write(text);

for (int i = 0; i < d.GetLength(); i++)

{

d.GetElement(i + 1, ref data);

Console.Write(data.ToString() + " ");

}

Console.WriteLine();

}

结果

双向链表也是可以有循环结构的

我就不实现了

循环结构可以通过一个结点遍历整个链表

双向链表也可以啊，虽然不是顺序性的

但也可以结合栈反序一下实现顺序性啊

具体需求，具体使用吧！

发表评论取消回复

登录 注册 找回密码

登录注册找回密码