自己手写一个双向链表【C风格】

//双链表
#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;//元素的类型
typedef int Status;//返回的状态类型

typedef struct DoubleNode
{
    struct DoubleNode* prior;
    ElemType data;
    struct DoubleNode* next;
}*DoubleList;//创建双链表

//初始化
Status InitList(DoubleList* L)
{
    *L = (DoubleList)malloc(sizeof(DoubleNode));
    if ((*L) == NULL)return ERROR;
    (*L)->next = NULL;
    (*L)->prior = NULL;
    return OK;
}
//获取长度
Status ListLength(DoubleList L)
{
    int length = 0;
    if (L == NULL) return length;
    while (L->next)
    {
        length++;
        L = L->next;
    }
    return length;
}
//获取某一个元素的位置
int GetElemIndex(DoubleList L, ElemType e)
{   
    int length = 1;
    if (L == NULL) return -1;
    while (L->next)
    {
        if (e == L->next->data)
            return length;
        L = L->next;
        length++;
    }
    return -1;
}
//获取某个位置的元素
Status GetElem(DoubleList L, int index, ElemType *e)
{
    if ( (L == NULL) || (index < 1) ) return ERROR;
    while (index--)
    {
        L = L->next;
        if (L == NULL)
            return ERROR;
    }
    *e = L->data;
    return OK;
}
//插入元素
Status ListInsert(DoubleList *L, int index, ElemType e)
{
    DoubleList q;
    if ( ((*L) == NULL) || (index > ListLength(*L) + 1) ||(index < 1) ) 
        return ERROR;
    //两种情况，链表为空还是不为空
    //在index之前一个位置操作，不容易出错
    if ((*L)->next != NULL && (index - 1 ) >0 )
    {
        *L = (*L)->next;
    }
    //开辟新节点的内存
    q = (DoubleList)malloc(sizeof(DoubleNode));
    if (q == NULL) return ERROR;
    q->data = e;
    
    //新节点连接前后节点
    q->next = (*L)->next;
    q->prior = (*L);

    //前后节点连接新节点
    if ((*L)->next)//如果后面是空节点不用连接，直接连接的是头结点
        (*L)->next->prior = q;//如果不加判断，会出现异常，NULL节点的前一节点不存在
    (*L)->next = q;

    return OK;   
}
//删除元素
Status ListDelete(DoubleList* L, int index)
{
    DoubleList p = *L, s;
    if (((*L) == NULL) || (index > ListLength(*L)) || (index < 1))
        return ERROR;
    while (index--)
    {
        p = p->next;//找到指定的位置节点
    }
    s = p->prior;//保存上一节点

    s->next = p->next;//指定删除的节点的前后节点互相连接
    p->next->prior = s;

    free(p);

    return OK;

}
//清空
Status ClearList(DoubleList* L)
{
    if ((*L) == NULL)
        return ERROR;
    DoubleList p = (*L)->next, s;
    int length = ListLength(*L);
    while (length--)
    {
        s = p;//保存现在的位置
        p = p->next;
        free(s);
    }
    (*L)->next = NULL;
    (*L)->prior = NULL;
    return OK;
}
//显示
Status ShowList(DoubleList L)
{
    if (L == NULL)
    {
        return ERROR;
    }
        
    int length = ListLength(L);
    while (length--)
    {
        L = L->next;
        printf("%d-->", L->data);
    }
    printf("已经全部显示\n");
    return OK;
}

int main()
{
    
    DoubleList L;
    ElemType e;

    //初始化
    InitList(&L);
    ShowList(L);
    printf("长度为:%d\n", ListLength(L));

    //插入节点
    for (int i = 1; i < 10; i++)
    {
        ListInsert(&L, 1, i);
    }
    ShowList(L);
    printf("长度为:%d\n", ListLength(L));

    //删除节点
    ListDelete(&L, 3);
    printf("删除第3个元素：\n");
    ShowList(L);
    printf("长度为:%d\n", ListLength(L));

    GetElem(L, 6, &e);
    printf("第6个元素的值为%d\n", e);

    printf("元素值为4的位置为：%d\n",GetElemIndex(L, 4));

    printf("清空所有元素\n");
    ClearList(&L);
    ShowList(L);
    printf("长度为:%d\n", ListLength(L));

    if (L)
        printf("只有空的头节点！\n");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189