#ifndef _DOUBLE_LINK_H#define _DOUBLE_LINK_H// 新建“雙向鏈表”。成功，返回表頭；否則，返回NULLextern int create_dlink();// 撤銷“雙向鏈表”。成功，返回0；否則，返回-1extern int destroy_dlink();// “雙向鏈表是否為空”。為空的話返回1；否則，返回0。extern int dlink_is_empty();// 返回“雙向鏈表的大小”extern int dlink_size();// 獲取“雙向鏈表中第index位置的元素”。成功，返回節點指針；否則，返回NULL。extern void* dlink_get(int index);// 獲取“雙向鏈表中第1個元素”。成功，返回節點指針；否則，返回NULL。extern void* dlink_get_first();// 獲取“雙向鏈表中最后1個元素”。成功，返回節點指針；否則，返回NULL。extern void* dlink_get_last();// 將“value”插入到index位置。成功，返回0；否則，返回-1。extern int dlink_insert(int index, void *pval);// 將“value”插入到表頭位置。成功，返回0；否則，返回-1。extern int dlink_insert_first(void *pval);// 將“value”插入到末尾位置。成功，返回0；否則，返回-1。extern int dlink_append_last(void *pval);// 刪除“雙向鏈表中index位置的節點”。成功，返回0；否則，返回-1extern int dlink_delete(int index);// 刪除第一個節點。成功，返回0；否則，返回-1extern int dlink_delete_first();// 刪除組后一個節點。成功，返回0；否則，返回-1extern int dlink_delete_last();#endif

#include <stdio.h>#include <malloc.h>/*** C 語言實現的雙向鏈表，能存儲任意數據。** @author skywang* @date 2013/11/07*/// 雙向鏈表節點typedef struct tag_node{struct tag_node *prev;struct tag_node *next;void* p;}node;// 表頭。注意，表頭不存放元素值?。?！static node *phead=NULL;// 節點個數。static int count=0;// 新建“節點”。成功，返回節點指針；否則，返回NULL。static node* create_node(void *pval){node *pnode=NULL;pnode = (node *)malloc(sizeof(node));if (!pnode){printf("create node error!/n");return NULL;}// 默認的，pnode的前一節點和后一節點都指向它自身pnode->prev = pnode->next = pnode;// 節點的值為pvalpnode->p = pval;return pnode;}// 新建“雙向鏈表”。成功，返回0；否則，返回-1。int create_dlink(){// 創建表頭phead = create_node(NULL);if (!phead)return -1;// 設置“節點個數”為0count = 0;return 0;}// “雙向鏈表是否為空”int dlink_is_empty(){return count == 0;}// 返回“雙向鏈表的大小”int dlink_size() {return count;}// 獲取“雙向鏈表中第index位置的節點”static node* get_node(int index){if (index<0 || index>=count){printf("%s failed! index out of bound!/n", __func__);return NULL;}// 正向查找if (index <= (count/2)){int i=0;node *pnode=phead->next;while ((i++) < index)pnode = pnode->next;return pnode;}// 反向查找int j=0;int rindex = count - index - 1;node *rnode=phead->prev;while ((j++) < rindex)rnode = rnode->prev;return rnode;}// 獲取“第一個節點”static node* get_first_node(){return get_node(0);}// 獲取“最后一個節點”static node* get_last_node(){return get_node(count-1);}// 獲取“雙向鏈表中第index位置的元素”。成功，返回節點值；否則，返回-1。void* dlink_get(int index){node *pindex=get_node(index);if (!pindex){printf("%s failed!/n", __func__);return NULL;}return pindex->p;}// 獲取“雙向鏈表中第1個元素的值”void* dlink_get_first(){return dlink_get(0);}// 獲取“雙向鏈表中最后1個元素的值”void* dlink_get_last(){return dlink_get(count-1);}// 將“pval”插入到index位置。成功，返回0；否則，返回-1。int dlink_insert(int index, void* pval){// 插入表頭if (index==0)return dlink_insert_first(pval);// 獲取要插入的位置對應的節點node *pindex=get_node(index);if (!pindex)return -1;// 創建“節點”node *pnode=create_node(pval);if (!pnode)return -1;pnode->prev = pindex->prev;pnode->next = pindex;pindex->prev->next = pnode;pindex->prev = pnode;// 節點個數+1count++;return 0;}// 將“pval”插入到表頭位置int dlink_insert_first(void *pval){node *pnode=create_node(pval);if (!pnode)return -1;pnode->prev = phead;pnode->next = phead->next;phead->next->prev = pnode;phead->next = pnode;count++;return 0;}// 將“pval”插入到末尾位置int dlink_append_last(void *pval){node *pnode=create_node(pval);if (!pnode)return -1;pnode->next = phead;pnode->prev = phead->prev;phead->prev->next = pnode;phead->prev = pnode;count++;return 0;}// 刪除“雙向鏈表中index位置的節點”。成功，返回0；否則，返回-1。int dlink_delete(int index){node *pindex=get_node(index);if (!pindex){printf("%s failed! the index in out of bound!/n", __func__);return -1;}pindex->next->prev = pindex->prev;pindex->prev->next = pindex->next;free(pindex);count--;return 0;}// 刪除第一個節點int dlink_delete_first(){return dlink_delete(0);}// 刪除組后一個節點int dlink_delete_last(){return dlink_delete(count-1);}// 撤銷“雙向鏈表”。成功，返回0；否則，返回-1。int destroy_dlink(){if (!phead){printf("%s failed! dlink is null!/n", __func__);return -1;}node *pnode=phead->next;node *ptmp=NULL;while(pnode != phead){ptmp = pnode;pnode = pnode->next;free(ptmp);}free(phead);phead = NULL;count = 0;return 0;}

#include <stdio.h>#include "double_link.h"/*** C 語言實現的雙向鏈表的測試程序。** (01) int_test()* 演示向雙向鏈表操作“int數據”。* (02) string_test()* 演示向雙向鏈表操作“字符串數據”。* (03) object_test()* 演示向雙向鏈表操作“對象”。** @author skywang* @date 2013/11/07*/// 雙向鏈表操作int數據void int_test(){int iarr[4] = {10, 20, 30, 40};printf("/n----%s----/n", __func__);create_dlink(); // 創建雙向鏈表dlink_insert(0, &iarr[0]); // 向雙向鏈表的表頭插入數據dlink_insert(0, &iarr[1]); // 向雙向鏈表的表頭插入數據dlink_insert(0, &iarr[2]); // 向雙向鏈表的表頭插入數據printf("dlink_is_empty()=%d/n", dlink_is_empty()); // 雙向鏈表是否為空printf("dlink_size()=%d/n", dlink_size()); // 雙向鏈表的大小// 打印雙向鏈表中的全部數據int i;int *p;int sz = dlink_size();for (i=0; i<sz; i++){p = (int *)dlink_get(i);printf("dlink_get(%d)=%d/n", i, *p);}destroy_dlink();}void string_test(){char* sarr[4] = {"ten", "twenty", "thirty", "forty"};printf("/n----%s----/n", __func__);create_dlink(); // 創建雙向鏈表dlink_insert(0, sarr[0]); // 向雙向鏈表的表頭插入數據dlink_insert(0, sarr[1]); // 向雙向鏈表的表頭插入數據dlink_insert(0, sarr[2]); // 向雙向鏈表的表頭插入數據printf("dlink_is_empty()=%d/n", dlink_is_empty()); // 雙向鏈表是否為空printf("dlink_size()=%d/n", dlink_size()); // 雙向鏈表的大小// 打印雙向鏈表中的全部數據int i;char *p;int sz = dlink_size();for (i=0; i<sz; i++){p = (char *)dlink_get(i);printf("dlink_get(%d)=%s/n", i, p);}destroy_dlink();}typedef struct tag_stu{int id;char name[20];}stu;static stu arr_stu[] ={{10, "sky"},{20, "jody"},{30, "vic"},{40, "dan"},};#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )void object_test(){printf("/n----%s----/n", __func__);create_dlink(); // 創建雙向鏈表dlink_insert(0, &arr_stu[0]); // 向雙向鏈表的表頭插入數據dlink_insert(0, &arr_stu[1]); // 向雙向鏈表的表頭插入數據dlink_insert(0, &arr_stu[2]); // 向雙向鏈表的表頭插入數據printf("dlink_is_empty()=%d/n", dlink_is_empty()); // 雙向鏈表是否為空printf("dlink_size()=%d/n", dlink_size()); // 雙向鏈表的大小// 打印雙向鏈表中的全部數據int i;int sz = dlink_size();stu *p;for (i=0; i<sz; i++){p = (stu *)dlink_get(i);printf("dlink_get(%d)=[%d, %s]/n", i, p->id, p->name);}destroy_dlink();}int main(){int_test(); // 演示向雙向鏈表操作“int數據”。string_test(); // 演示向雙向鏈表操作“字符串數據”。object_test(); // 演示向雙向鏈表操作“對象”。return 0;}

----int_test----dlink_is_empty()=0dlink_size()=3dlink_get(0)=30dlink_get(1)=20dlink_get(2)=10----string_test----dlink_is_empty()=0dlink_size()=3dlink_get(0)=thirtydlink_get(1)=twentydlink_get(2)=ten----object_test----dlink_is_empty()=0dlink_size()=3dlink_get(0)=[30, vic]dlink_get(1)=[20, jody]dlink_get(2)=[10, sky]

#ifndef DOUBLE_LINK_HXX#define DOUBLE_LINK_HXX#include <iostream>using namespace std;template<class T>struct DNode{public:T value;DNode *prev;DNode *next;public:DNode() { }DNode(T t, DNode *prev, DNode *next) {this->value = t;this->prev = prev;this->next = next;}};template<class T>class DoubleLink{public:DoubleLink();~DoubleLink();int size();int is_empty();T get(int index);T get_first();T get_last();int insert(int index, T t);int insert_first(T t);int append_last(T t);int del(int index);int delete_first();int delete_last();private:int count;DNode<T> *phead;private:DNode<T> *get_node(int index);};template<class T>DoubleLink<T>::DoubleLink() : count(0){// 創建“表頭”。注意：表頭沒有存儲數據！phead = new DNode<T>();phead->prev = phead->next = phead;// 設置鏈表計數為0//count = 0;}// 析構函數template<class T>DoubleLink<T>::~DoubleLink(){// 刪除所有的節點DNode<T>* ptmp;DNode<T>* pnode = phead->next;while (pnode != phead){ptmp = pnode;pnode=pnode->next;delete ptmp;}// 刪除"表頭"delete phead;phead = NULL;}// 返回節點數目template<class T>int DoubleLink<T>::size(){return count;}// 返回鏈表是否為空template<class T>int DoubleLink<T>::is_empty(){return count==0;}// 獲取第index位置的節點template<class T>DNode<T>* DoubleLink<T>::get_node(int index){// 判斷參數有效性if (index<0 || index>=count){cout << "get node failed! the index in out of bound!" << endl;return NULL;}// 正向查找if (index <= count/2){int i=0;DNode<T>* pindex = phead->next;while (i++ < index) {pindex = pindex->next;}return pindex;}// 反向查找int j=0;int rindex = count - index -1;DNode<T>* prindex = phead->prev;while (j++ < rindex) {prindex = prindex->prev;}return prindex;}// 獲取第index位置的節點的值template<class T>T DoubleLink<T>::get(int index){return get_node(index)->value;}// 獲取第1個節點的值template<class T>T DoubleLink<T>::get_first(){return get_node(0)->value;}// 獲取最后一個節點的值template<class T>T DoubleLink<T>::get_last(){return get_node(count-1)->value;}// 將節點插入到第index位置之前template<class T>int DoubleLink<T>::insert(int index, T t){if (index == 0)return insert_first(t);DNode<T>* pindex = get_node(index);DNode<T>* pnode = new DNode<T>(t, pindex->prev, pindex);pindex->prev->next = pnode;pindex->prev = pnode;count++;return 0;}// 將節點插入第一個節點處。template<class T>int DoubleLink<T>::insert_first(T t){DNode<T>* pnode = new DNode<T>(t, phead, phead->next);phead->next->prev = pnode;phead->next = pnode;count++;return 0;}// 將節點追加到鏈表的末尾template<class T>int DoubleLink<T>::append_last(T t){DNode<T>* pnode = new DNode<T>(t, phead->prev, phead);phead->prev->next = pnode;phead->prev = pnode;count++;return 0;}// 刪除index位置的節點template<class T>int DoubleLink<T>::del(int index){DNode<T>* pindex = get_node(index);pindex->next->prev = pindex->prev;pindex->prev->next = pindex->next;delete pindex;count--;return 0;}// 刪除第一個節點template<class T>int DoubleLink<T>::delete_first(){return del(0);}// 刪除最后一個節點template<class T>int DoubleLink<T>::delete_last(){return del(count-1);}#endif

#include <iostream>#include "DoubleLink.h"using namespace std;// 雙向鏈表操作int數據void int_test(){int iarr[4] = {10, 20, 30, 40};cout << "/n----int_test----" << endl;// 創建雙向鏈表DoubleLink<int>* pdlink = new DoubleLink<int>();pdlink->insert(0, 20); // 將 20 插入到第一個位置pdlink->append_last(10); // 將 10 追加到鏈表末尾pdlink->insert_first(30); // 將 30 插入到第一個位置// 雙向鏈表是否為空cout << "is_empty()=" << pdlink->is_empty() <<endl;// 雙向鏈表的大小cout << "size()=" << pdlink->size() <<endl;// 打印雙向鏈表中的全部數據int sz = pdlink->size();for (int i=0; i<sz; i++)cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;}void string_test(){string sarr[4] = {"ten", "twenty", "thirty", "forty"};cout << "/n----string_test----" << endl;// 創建雙向鏈表DoubleLink<string>* pdlink = new DoubleLink<string>();pdlink->insert(0, sarr[1]); // 將 sarr中第2個元素 插入到第一個位置pdlink->append_last(sarr[0]); // 將 sarr中第1個元素 追加到鏈表末尾pdlink->insert_first(sarr[2]); // 將 sarr中第3個元素 插入到第一個位置// 雙向鏈表是否為空cout << "is_empty()=" << pdlink->is_empty() <<endl;// 雙向鏈表的大小cout << "size()=" << pdlink->size() <<endl;// 打印雙向鏈表中的全部數據int sz = pdlink->size();for (int i=0; i<sz; i++)cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;}struct stu{int id;char name[20];};static stu arr_stu[] ={{10, "sky"},{20, "jody"},{30, "vic"},{40, "dan"},};#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )void object_test(){cout << "/n----object_test----" << endl;// 創建雙向鏈表DoubleLink<stu>* pdlink = new DoubleLink<stu>();pdlink->insert(0, arr_stu[1]); // 將 arr_stu中第2個元素 插入到第一個位置pdlink->append_last(arr_stu[0]); // 將 arr_stu中第1個元素 追加到鏈表末尾pdlink->insert_first(arr_stu[2]); // 將 arr_stu中第3個元素 插入到第一個位置// 雙向鏈表是否為空cout << "is_empty()=" << pdlink->is_empty() <<endl;// 雙向鏈表的大小cout << "size()=" << pdlink->size() <<endl;// 打印雙向鏈表中的全部數據int sz = pdlink->size();struct stu p;for (int i=0; i<sz; i++){p = pdlink->get(i);cout << "pdlink("<<i<<")=[" << p.id << ", " << p.name <<"]" <<endl;}}int main(){int_test(); // 演示向雙向鏈表操作“int數據”。string_test(); // 演示向雙向鏈表操作“字符串數據”。object_test(); // 演示向雙向鏈表操作“對象”。return 0;}

----int_test----is_empty()=0size()=3pdlink(0)=30pdlink(1)=20pdlink(2)=10----string_test----is_empty()=0size()=3pdlink(0)=thirtypdlink(1)=twentypdlink(2)=ten----object_test----is_empty()=0size()=3pdlink(0)=[30, vic]pdlink(1)=[20, jody]pdlink(2)=[10, sky]

/*** Java 實現的雙向鏈表。* 注：java自帶的集合包中有實現雙向鏈表，路徑是:java.util.LinkedList** @author skywang* @date 2013/11/07*/public class DoubleLink<T> {// 表頭private DNode<T> mHead;// 節點個數private int mCount;// 雙向鏈表“節點”對應的結構體private class DNode<T> {public DNode prev;public DNode next;public T value;public DNode(T value, DNode prev, DNode next) {this.value = value;this.prev = prev;this.next = next;}}// 構造函數public DoubleLink() {// 創建“表頭”。注意：表頭沒有存儲數據！mHead = new DNode<T>(null, null, null);mHead.prev = mHead.next = mHead;// 初始化“節點個數”為0mCount = 0;}// 返回節點數目public int size() {return mCount;}// 返回鏈表是否為空public boolean isEmpty() {return mCount==0;}// 獲取第index位置的節點private DNode<T> getNode(int index) {if (index<0 || index>=mCount)throw new IndexOutOfBoundsException();// 正向查找if (index <= mCount/2) {DNode<T> node = mHead.next;for (int i=0; i<index; i++)node = node.next;return node;}// 反向查找DNode<T> rnode = mHead.prev;int rindex = mCount - index -1;for (int j=0; j<rindex; j++)rnode = rnode.prev;return rnode;}// 獲取第index位置的節點的值public T get(int index) {return getNode(index).value;}// 獲取第1個節點的值public T getFirst() {return getNode(0).value;}// 獲取最后一個節點的值public T getLast() {return getNode(mCount-1).value;}// 將節點插入到第index位置之前public void insert(int index, T t) {if (index==0) {DNode<T> node = new DNode<T>(t, mHead, mHead.next);mHead.next.prev = node;mHead.next = node;mCount++;return ;}DNode<T> inode = getNode(index);DNode<T> tnode = new DNode<T>(t, inode.prev, inode);inode.prev.next = tnode;inode.next = tnode;mCount++;return ;}// 將節點插入第一個節點處。public void insertFirst(T t) {insert(0, t);}// 將節點追加到鏈表的末尾public void appendLast(T t) {DNode<T> node = new DNode<T>(t, mHead.prev, mHead);mHead.prev.next = node;mHead.prev = node;mCount++;}// 刪除index位置的節點public void del(int index) {DNode<T> inode = getNode(index);inode.prev.next = inode.next;inode.next.prev = inode.prev;inode = null;mCount--;}// 刪除第一個節點public void deleteFirst() {del(0);}// 刪除最后一個節點public void deleteLast() {del(mCount-1);}}

/*** Java 實現的雙向鏈表。* 注：java自帶的集合包中有實現雙向鏈表，路徑是:java.util.LinkedList** @author skywang* @date 2013/11/07*/public class DlinkTest {// 雙向鏈表操作int數據private static void int_test() {int[] iarr = {10, 20, 30, 40};System.out.println("/n----int_test----");// 創建雙向鏈表DoubleLink<Integer> dlink = new DoubleLink<Integer>();dlink.insert(0, 20); // 將 20 插入到第一個位置dlink.appendLast(10); // 將 10 追加到鏈表末尾dlink.insertFirst(30); // 將 30 插入到第一個位置// 雙向鏈表是否為空System.out.printf("isEmpty()=%b/n", dlink.isEmpty());// 雙向鏈表的大小System.out.printf("size()=%d/n", dlink.size());// 打印出全部的節點for (int i=0; i<dlink.size(); i++)System.out.println("dlink("+i+")="+ dlink.get(i));}private static void string_test() {String[] sarr = {"ten", "twenty", "thirty", "forty"};System.out.println("/n----string_test----");// 創建雙向鏈表DoubleLink<String> dlink = new DoubleLink<String>();dlink.insert(0, sarr[1]); // 將 sarr中第2個元素 插入到第一個位置dlink.appendLast(sarr[0]); // 將 sarr中第1個元素 追加到鏈表末尾dlink.insertFirst(sarr[2]); // 將 sarr中第3個元素 插入到第一個位置// 雙向鏈表是否為空System.out.printf("isEmpty()=%b/n", dlink.isEmpty());// 雙向鏈表的大小System.out.printf("size()=%d/n", dlink.size());// 打印出全部的節點for (int i=0; i<dlink.size(); i++)System.out.println("dlink("+i+")="+ dlink.get(i));}// 內部類private static class Student {private int id;private String name;public Student(int id, String name) {this.id = id;this.name = name;}@Overridepublic String toString() {return "["+id+", "+name+"]";}}private static Student[] students = new Student[]{new Student(10, "sky"),new Student(20, "jody"),new Student(30, "vic"),new Student(40, "dan"),};private static void object_test() {System.out.println("/n----object_test----");// 創建雙向鏈表DoubleLink<Student> dlink = new DoubleLink<Student>();dlink.insert(0, students[1]); // 將 students中第2個元素 插入到第一個位置dlink.appendLast(students[0]); // 將 students中第1個元素 追加到鏈表末尾dlink.insertFirst(students[2]); // 將 students中第3個元素 插入到第一個位置// 雙向鏈表是否為空System.out.printf("isEmpty()=%b/n", dlink.isEmpty());// 雙向鏈表的大小System.out.printf("size()=%d/n", dlink.size());// 打印出全部的節點for (int i=0; i<dlink.size(); i++) {System.out.println("dlink("+i+")="+ dlink.get(i));}}public static void main(String[] args) {int_test(); // 演示向雙向鏈表操作“int數據”。string_test(); // 演示向雙向鏈表操作“字符串數據”。object_test(); // 演示向雙向鏈表操作“對象”。}}

----int_test----isEmpty()=falsesize()=3dlink(0)=30dlink(1)=20dlink(2)=10----string_test----isEmpty()=falsesize()=3dlink(0)=thirtydlink(1)=twentydlink(2)=ten----object_test----isEmpty()=falsesize()=3dlink(0)=[30, vic]dlink(1)=[20, jody]dlink(2)=[10, sky]