数据结构：实现LinkedList

数据结构

版本：2
作者：陈小默

如果之前学习过java的话，一定接触过其中的ArrayList和LinkedList。当我们说起其中的区别时，大部分人的回答都是面试宝典的标准答案：一个内部实现是数组，另一个内部实现是链表，一个查找快，另一个增删快。至于为什么是这样的，许多人就回答不上来了。所以，我们现在就是要亲自动手制造一个简易的LinkedList来学习其中的原理。

定义需求

我们仿照Java中的实现，定义以下需求：

作为类

LinkedList应该具有初始化器和析构函数，能够在创建时进行初始化和结束时销毁数据。

    LinkedList();
    ~LinkedList();

作为List

LinkedList应该具有添加数据，获得数据，移除数据的基本功能。

    void add(Any * data);
    Any * get(int index);
    bool add(int index,Any * data);
    void addFirst(Any* data);
    void addLast(Any* data);
    Any * remove(int index);
    Any * removeFirst();
    Any * removeLast();
    int size();

作为栈stack

LinkedList应该具有入栈和出栈的功能。

    Any * pop();
    void push(Any * data);

作为队列

LinkedList应该具有入队列和出队列的功能。

    void in(Any * data);
    Any * out();

定义模版

我们的LinkedList不能只存放固定类型的数据，所以我们需要定义泛型模版，来处理不同的存储需求

template<class Any>

定义数据结构

由于内部实现方式是链表，所以我们需要定义一个双向链表结点Node

template<class Any>
struct Node{
    Node<Any> * prior;
    Any * data;
    Node<Any> * next;
};

其中prior指向前一个结点，data指向存储的数据，next指向下一个结点。

声明类

当我们一切准备就绪之后我们可以写我们的头文件了LinkedList.h

#ifndef LINKED_LIST_H_
#define LINKED_LIST_H_
template<class Any>
struct Node{
    Node<Any> * prior;
    Any * data;
    Node<Any> * next;
};
template<class Any>
class LinkedList{
    Node<Any> * head;//头结点
    Node<Any> * tail;//尾结点
    int length;//链表长度
    Node<Any> * getNode(int index){
        //获得index位置的结点数据
        if(index<0||index>length){
            return NULL;
        }else{
            Node<Any> *temp = head->next;
            for(int i=0;i<index;i++,temp=temp->next);
            return temp;
        }
    };
public:
    LinkedList();
    ~LinkedList();
    //list
    void add(Any * data);//添加数据
    Any * get(int index);//获取index位置上的数据
    bool add(int index,Any * data);//向index位置上添加一条数据
    void addFirst(Any* data);//向链表头部添加一条数据
    void addLast(Any* data);//向链表尾部添加一条数据
    Any * remove(int index);//移除index位置上的数据
    Any * removeFirst();//移除链表第一个元素
    Any * removeLast();//移除链表最后一个元素
    int size();//获得链表的长度
    //stack
    Any * pop();//出栈一条数据
    void push(Any * data);//入栈一条数据
    //queue
    void in(Any * data);//进入队列
    Any * out();//出队列
};
#endif

方法实现

这里由于我使用的环境是Visual Studio 2010 ，其中并不支持较高的C++标准。而在较低的版本中我们的模板并不支持与源文件的分离，也就是说如果我在另一个源文件中实现这个类将无法通过编译，但是较高版本的编译环境可以通过给模板添加export 关键字来使声明与定义分离。注意：是给每一个模板添加export关键字。

#ifdef STACKTP_H_
#define STACKTP_H_
export template<class T>
class Stack
{......};
#endif

但是这里我就将实现放在了头文件中，也就是说下面的所有代码均在头文件实现在#endid之前，有条件的可以另起一个源文件。
接下来我们一个方法一个方法的去分析
1，

template<class Any>
LinkedList<Any>::LinkedList(){
    head = new Node<Any>;
    tail = new Node<Any>;
    head->data = NULL;
    head->next = tail;
    head->prior = NULL;
    tail->data=NULL;
    tail->prior=head;
    tail->next=NULL;
    length=0;
}

对于我们的构造方法，其中最主要的作用就是初始化结点。当我们创建列表对象的时候，需要创建一个空的头结点和一个空的尾结点，这两个空结点没有数据。头结点的后继指向尾结点，尾结点的前驱指向头结点。因为头结点只是表示链表的开始，尾结点表示链表的结束。所以该结点不计入长度，并且其中的数据指针也永远不会存储数据。
2，

template<class Any>
LinkedList<Any>::~LinkedList(){
    for(int i=0;i<length+2;i++){
        Node<Any> * temp = head;
        head = head->next;
        Any * data = temp->data;
        if(data!=NULL){
            delete data;
        }
        delete temp;
    }
}

这是这个类的析构函数，其目的就是在销毁链表的时候同时销毁其中存储的数据。以免造成内存泄漏。注意我们销毁之前必须先移动头指针到下一个位置，否则该结点销毁之后我们就无法再取出下一个结点的指针了。同理，我们在销毁结点之前必须先销毁数据。
3，

template<class Any>
void LinkedList<Any>::add(Any * data){
    addLast(data);
}

由于我们的插入位置是最后，所以可以直接调用addLast()方法。如果我们不想让新加入的数据存放在最后也可以自定义。
4，

template<class Any>
Any * LinkedList<Any>::get(int index){
    Node<Any>* temp = getNode(index);
    if(temp==NULL){
        return NULL;
    }else{
        return temp->data;
    }
}

这个方法的目的就是获取index结点的数据。这里需要提醒的是，我们仅仅是获取了引用，数据引用仍然在链表中存在，所以我们delete链表的时候一定要小心，以免造成在get出来的数据在delete链表之后发生空指针错误。
5，

template<class Any>
bool LinkedList<Any>::add(int index,Any * data){
    if(index<0||index>length){
        return false;
    }else if(index==0){
        addFirst(data);
    }else if(index==length){
        addLast(data);
    }else{
        Node<Any> *temp = getNode(index-1);
        Node<Any> *node = new Node<Any>;
        node->data=data;
        node->prior=temp;
        node->next=temp->next;
        temp->next->prior=node;
        temp->next=node;
        length++;
    }
    return true;
}

这个方法的目的是将数据插入index位置。我们先要判断用户传入的index是否合法，不合法返回false。另外我们的判断还有一个作用就是去选择性的调用插入头部或者是尾部。现在我们解释最后一个else的作用：获得我们要插入的位置的前一个结点，然后通过指针移动去将自身节点插入到原链表的中间位置。实现时一定要注意操作指针的顺序，以免指针丢失。
6，

template<class Any>
void LinkedList<Any>::addFirst(Any* data){
    Node<Any> * node = new Node<Any>;
    node->data=data;
    node->prior=head;;
    node->next=head->next;
    node->next->prior=node;
    head->next=node;
    length++;
}

通过这个实现我们能够看出头结点的作用仅仅是表示链表的开始，其中有效数据存储在头结点之后，并且在我们增加了头尾结点后，并不需要我们去判断头尾指针是否重合。
7，

template<class Any>
void LinkedList<Any>::addLast(Any* data){
    Node<Any> * node = new Node<Any>;
    node->data=data;
    node->next=tail;
    node->prior=tail->prior;
    node->prior->next=node;
    tail->prior=node;
    length++;
}

解释同方法6
8，

template<class Any>
Any * LinkedList<Any>::remove(int index){
    if(index<0||index>length){
        return NULL;
    }else if(index==0){
        return removeFirst();
    }else if(index==length){
        return removeLast();
    }else{
        Node<Any> *temp = getNode(index);
        if(temp==NULL){
            return NULL:
        }else{
            Any * data = temp->data;
            delete temp;
            length--;
            return data;
        }
    }
}

这里的remove方法在返回数据后删除结点，但是不会删除数据，所以如果我们需要在delete链表之后还能正常使用数据的话，应该在delete链表之前，使用remove方法移出数据。
9，

template<class Any>
Any * LinkedList<Any>::removeFirst(){
    if(length==0){
        return NULL;
    }else{
        Node<Any> * temp = head->next;
        Any * data = temp->data;
        head->next=temp->next;
        head->next->prior=head;
        delete temp;
        length--;
        return data;
    }
}

这个方法跟remove方法相同，其移除链表中的第一条数据。注意这里移除的是头结点后的第一个结点而不是头结点。
10，

template<class Any>
Any * LinkedList<Any>::removeLast(){
    if(length==0){
        return NULL;
    }else{
        Node<Any> * temp = tail->prior;
        Any* data = temp->data;
        tail->prior=temp->prior;
        tail->prior->next=tail;
        delete temp;
        length--;
        return data;
    }
}

同上，移除链表的最后一条数据。移除的是尾结点前的第一个结点，而不是尾结点。
11，

template<class Any>
int LinkedList<Any>::size(){
    return length;
}

这个方法不用解释了吧。
12，

template<class Any>
Any * LinkedList<Any>::pop(){
    return removeLast();
}
template<class Any>
void LinkedList<Any>::push(Any * data){
    addLast(data);
}

这是栈实现方法，符合先进后出
13，

template<class Any>
void LinkedList<Any>::in(Any * data){
    addLast(data);
}
template<class Any>
Any * LinkedList<Any>::out(){
    return removeFirst();
}

这是队列的实现，符合先进先出。

到这里一个能够存储数据的链表就创造完成了。下面我们演示一下能否正常运行。

演示

这里我使用的对象是之前博客创建的学生类。简单了解一下，其中的show()方法会计算平均成绩并打印，被销毁时也会打印一句话。

用作一般数据存储

#include "stdafx.h"
#include "student.h"
#include "LinkedList.h"
int _tmain(int argc, _TCHAR* argv[]){
    LinkedList<Student> * list = new LinkedList<Student>();
    list->add(new Student("Jack",98,99,100));
    list->add(new Student("Sam",99,90,99));
    list->add(new Student("Sue",97,99,87));
    for(int i=0;i<list->size();i++){
        list->get(i)->show();
    }
    delete list;
    return 0;
}

以下是输出结果，从结果中可以看出list结束时，释放了其中的全部内存空间

Jack 同学的语文成绩为98分，数学成绩为100分，英语成绩为99分，平均成绩99.0分
Sam 同学的语文成绩为99分，数学成绩为99分，英语成绩为90分，平均成绩96.0分
Sue 同学的语文成绩为97分，数学成绩为87分，英语成绩为99分，平均成绩94.3分
再见! Jack.
再见! Sam.
再见! Sue.
请按任意键继续. . .

用作栈

#include "stdafx.h"
#include "student.h"
#include "LinkedList.h"
int _tmain(int argc, _TCHAR* argv[]){
    LinkedList<Student> * list = new LinkedList<Student>();
    list->push(new Student("Jack",98,99,100));
    list->push(new Student("Sam",99,90,99));
    list->push(new Student("Sue",97,99,87));
    list->pop()->show();
    list->pop()->show();
    list->pop()->show();
    delete list;
    return 0;
}

以下是输出结果：可以看到其符合先入后出的规则。

Sue 同学的语文成绩为97分，数学成绩为87分，英语成绩为99分，平均成绩94.3分
Sam 同学的语文成绩为99分，数学成绩为99分，英语成绩为90分，平均成绩96.0分
Jack 同学的语文成绩为98分，数学成绩为100分，英语成绩为99分，平均成绩99.0分
请按任意键继续. . .

用作队列

#include "stdafx.h"
#include "student.h"
#include "LinkedList.h"
int _tmain(int argc, _TCHAR* argv[]){
    LinkedList<Student> * list = new LinkedList<Student>();
    list->in(new Student("Jack",98,99,100));
    list->in(new Student("Sam",99,90,99));
    list->in(new Student("Sue",97,99,87));
    list->out()->show();
    list->out()->show();
    list->out()->show();
    delete list;
    return 0;
}

以下是输出结果：符合先进先出

Jack 同学的语文成绩为98分，数学成绩为100分，英语成绩为99分，平均成绩99.0分
Sam 同学的语文成绩为99分，数学成绩为99分，英语成绩为90分，平均成绩96.0分
Sue 同学的语文成绩为97分，数学成绩为87分，英语成绩为99分，平均成绩94.3分
请按任意键继续. . .