双链表

#ifndef _LINK_NODE_
#define _LINKE_NODE_

typedef struct Node {

  struct Node* pNext;
  struct Node* pPrevious;
  void* pData;

} NodeStruct, *pNodeStruct;




typedef struct SingleLinkedList {

  pNodeStruct pHead;

  pNodeStruct pTail;

} SingleLinkedListStruct, *pSingleLinkedListStruct;

typedef int (*CompareFunc)(void*,void*)  ;

void init(pSingleLinkedListStruct*);
void destory(pSingleLinkedListStruct*);
void display(pSingleLinkedListStruct);
void insertFront(pSingleLinkedListStruct*,void*);
void insertTail(pSingleLinkedListStruct*,void*);
pNodeStruct* findData(pSingleLinkedListStruct*,void*,CompareFunc);
void deleteNode(pSingleLinkedListStruct*,void*,CompareFunc);
 
int cmp(void* a,void* b)
{
	int* pa=(int*)a;
	int* pb=(int*)b;
	if((*pa)==(*pb))
	{
		return 1;
	}else 
		return 0;
}
#endif

 

 

 

#include <stdio.h>
#include <malloc.h>
#include "link.h"


int main()
{
	int a=90,b=80,c=20,d=2,e=2;
	pSingleLinkedListStruct pt=(pSingleLinkedListStruct)malloc(sizeof(SingleLinkedListStruct));
	init(&pt);
 
	insertFront(&pt,&a);//前增
	insertFront(&pt,&b);
	insertFront(&pt,&c);
	 insertTail(&pt,&d);//后增
	//pNodeStruct* p1=findData(&pt,&e,cmp);//查找,返回找到的地址；
	//int* t=(int*)(*p1)->pPrevious->pData;
	//printf("%d\n",(*t));//打印查找到的值
 
printf("------删除前--------\n");	
	display(pt);
	deleteNode(&pt,&a,cmp);//删除调用的查找的方法
	 
printf("------删除后--------\n");		
	display(pt);


	destory(&pt);
	 
    return 0;
}


 
void init(pSingleLinkedListStruct* ps)
{
	(*ps)->pHead=NULL;
	(*ps)->pTail=NULL;
}




void display(pSingleLinkedListStruct p)
{
	pNodeStruct currentNode=p->pHead;
	while(currentNode)
	{
		printf("%d\n",*(int*)(currentNode->pData));
		currentNode=currentNode->pNext;
	}
}

void insertFront(pSingleLinkedListStruct* p,void* data)
{
        pNodeStruct currentNode=(pNodeStruct)malloc(sizeof(NodeStruct));
		currentNode->pData=data;
        if((*p)->pHead==NULL)
        {
			currentNode->pNext=NULL;
			currentNode->pPrevious=NULL;
			(*p)->pHead=currentNode;
			(*p)->pTail=currentNode;

        }
		else
		{
			currentNode->pNext=(*p)->pHead;
			(*p)->pHead->pPrevious=currentNode;
			(*p)->pHead=currentNode;
		}
}

void insertTail(pSingleLinkedListStruct* p,void* data)
{
	pNodeStruct currentNode=(pNodeStruct)malloc(sizeof(NodeStruct));
	currentNode->pData=data;
	if((*p)->pTail==NULL)
	{
			currentNode->pNext=NULL;
			currentNode->pPrevious=NULL;
			(*p)->pHead=currentNode;
			(*p)->pTail=currentNode;
	}
	else
	{
			currentNode->pNext=NULL;
			currentNode->pPrevious=(*p)->pTail;
			(*p)->pTail->pNext=currentNode;
			(*p)->pTail=currentNode;
	}

}


pNodeStruct* findData(pSingleLinkedListStruct* p,void* data,CompareFunc compar)
{
	pNodeStruct cp=(*p)->pHead;
	while(cp)
	{
		if(compar(cp->pData,data))
		{
			 
			return &cp;
		}
		cp=cp->pNext;
	}
	return NULL;

}

//之前单链表的方式是记住前一个节点。双链表不需要记住前一个节点
void deleteNode(pSingleLinkedListStruct* p,void* data,CompareFunc compar)
{
	pNodeStruct* searchNode=findData(p,data,cmp);//调用查找方法
	if(searchNode==NULL)
		return;
	if((*searchNode)==(*p)->pHead)
	{
		(*p)->pHead=(*p)->pHead->pNext;
		(*p)->pHead->pPrevious=NULL;
		printf("头结点要被删掉了\n");
		 
	}else if((*searchNode)==(*p)->pTail)
	{	
		(*p)->pTail=(*p)->pTail->pPrevious;
		(*p)->pTail->pNext=NULL;
		printf("尾结点要被删掉了\n");
		 

		
	}else
	{
		 (*searchNode)->pPrevious->pNext=(*searchNode)->pNext;
		(*searchNode)->pNext->pPrevious=(*searchNode)->pPrevious;
	}
	
	 
}

void destory(pSingleLinkedListStruct* p)
{
	pNodeStruct cp=(*p)->pHead;
	if((*p)->pHead!=NULL)
	{
		cp=(*p)->pHead->pNext;
		free((*p)->pHead);
		(*p)->pHead=cp;
	}
}