雙向鏈表

double?link?list

typedef struct dou_node {
DATATYPE data;
struct dou_node *prev;
struct dou_node *next;
}DouLinkNode;

---

雙向鏈表：

節點? =? 數據?+?NEXT?+PREV?.
手撕代碼(增加+刪除)
增加，刪除的操作，?需要 tmp?停止待操作節點的前一節點上。
查找操作進行了擴展，回調函數(函數指針)。解耦合，擴展功能。

---

查找? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?順序表O(1)? ? ? ? ?鏈表??O(n)
插入和刪除? ? ? ? ? ? ? ? ? ? ?順序表?O(n)? ? ? ?鏈表???O(1)

空間性能
順序表? ? ? ? ? 需要預先分配空間，大小固定
鏈表? ?? ? ? ? ? 不需要預先分配，大小可變，動態分配

---

int InsertHeadDouLinkList(DouLinkList *list,DATATYPE *data)
{
DouLinkNode *newnode = (DouLinkNode*)malloc(sizeof(DouLinkNode));
if ( NULL == newnode )
{
perror( "IsertHeadDouLinkList malloc error" );
return 1;
}
? memcpy(&newnode->data,data,sizeof(DATATYPE));
newnode->prev = NULL;
newnode->next = NULL;
if ( IsEmptyLinkList(list) )
{
list->head = newnode;
}
else{
newnode->next = list->head;
? list->head->prev = newnode;
list->head = newnode;
}
list->clen++;
return 0;
}

int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data)
{
if (IsEmptyLinkList(dl))
{
return InsertHeadDouLinkList(dl, data);
}
else
{
DouLinkNode *newnode = malloc(sizeof(DouLinkNode));
if (NULL == newnode)
{
perror("InsertTailDouLinkList malloc");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
newnode->prev = NULL;

? ? DouLinkNode *tmp = dl->head;
while (tmp->next)
{
tmp = tmp->next;
}

? ? newnode->prev = tmp;
tmp->next = newnode;
}
dl->clen++;
return 0;
}

int InsertPosLinkList(DouLinkList *list, DATATYPE *data,int pos)
{
if(pos<0 || pos > list->clen)
{
printf("InsertPosLinkList pos error\n");
return 1;
}

? ? if(pos == 0)
{
return InsertHeadDouLinkList(list,data);
}
else if(pos == list->clen)
{
return InsertTailDouLinkList(list, data);
}else
{

? ? DouLinkNode *newnode = malloc(sizeof(DouLinkNode));
if(NULL == newnode)
{
perror("InsertPosLinkList malloc error");
return 1;
}
memcpy(&newnode->data,data,sizeof(DATATYPE));
newnode->next = NULL;
newnode->prev = NULL;
DouLinkNode *tmp = list->head;
for(int i = 0; i < pos; i++)
{
tmp = tmp->next;
}

? ? newnode->next = tmp;
newnode->prev = tmp->prev;
tmp->prev->next = newnode;
tmp->prev = newnode;
list->clen++;

? ? }
return 0;
}

---

gdb

---

typedef enum {DIR_FORWARD,DIR_BACKWARD}DIRECT;? ? //枚舉

int ShowLinkList(DouLinkList *list,DIRECT direct)??
{
DouLinkNode *tmp = list->head;
if(DIR_FORWARD == direct)
{
while(tmp)
{
printf("%s \n",tmp->data.data);
tmp = tmp->next;
}

? ? }else
{
while(tmp->next)
{
tmp = tmp->next;
}? // 移到最后
while(tmp)
{
printf("%s \n",tmp->data.data);
tmp = tmp->prev;
} ? ? ?
}

return 0;
}

int ReviseLinkList(DouLinkList *list)
{
if(list == NULL|| list->clen == 0)
{
printf("RviseLinkList error");
return 1;
}
DouLinkNode *prev = NULL;
DouLinkNode *curr = list->head;
DouLinkNode *next = NULL;

while(curr!=NULL)
{
? next = curr->next;
prev = curr->prev;
curr->next = prev; //后移
prev = curr;
curr = next;
}
list->head = prev;
return 0;
}

---

DouLinkNode *FindDouLinkList(DouLinkList *dl,PFUN fun, void*arg);

DouLinkNode *FindDouLinkList(DouLinkList *dl,PFUN fun, void*arg)
{
DouLinkNode* tmp = dl->head;
while(tmp)
{
// if(0==strcmp(tmp->data.name,name))
if ( fun ( &tmp->data , arg))
{
return tmp;
}
tmp=tmp->next;
}
return NULL;
}

int findperbyname(DATATYPE*data,void* arg)
{
// 從void* -> 其他類型指針，需要強轉
return 0 == strcmp(data->name,(char*)arg);
}

int findperbyage(DATATYPE*data,void* arg)
{
// 從void* -> 其他類型指針，需要強轉
return data->age == *(int*)arg;;
}

---

? ?printf("------------------------find-----------------------------\n");
char want_name[] = "lisi";
int age =50;
DouLinkNode* tmp = FindDouLinkList(list,findperbyname ,want_name);
if (NULL == tmp)
{
printf("cant find per %s\n",want_name);
}
else
{
printf("find it,name:%s score:%d\n",tmp->data.name,tmp->data.score);
}