双链表【参照redis链表结构】

佚名 5年前 (2020-03-23) 算法 605人围观抢沙发百度已收录

参照了Redis里面的双链表结构，可以说是完全复制粘贴，redis的双链表还是写的很通俗易懂的，没有什么花里胡哨的东西，但是redis还有个iter迭代器的结构来遍历链表。我这里就没有实现了，只是实现了双链表的基本操作

redis双链表结构有如下特点

多态：可以储存多种数据类型
双端
无环：也就是说head->pre==NULL tail->next=NULL
带有长度计数器
有头指针和尾指针

实现

#include<iostream>
#include<stdlib.h>
using namespace std;




struct listNode{
	listNode* prev;
	listNode* next;
	int value;  //可以是void  void*类型 实现多态链表 
};

struct list{
	listNode* head;
	listNode* tail;
	int len;
}; 

//初始化链表 
list* listCreate(){
	list* myList;
	myList = (list*)malloc(sizeof(list)); 
	myList->head = myList->tail=NULL;
	myList->len=0;
	return myList; 
} 

//移除链表元素 
void listEmpty(list* list){
	int len = 0;
	listNode* current,*next;
	current = list->head;
	while(len--){
		next = current->next;
		free(current);
		current = next;
	}
	list->head=list->tail=NULL;
	list->len=0;
} 

void listRelease(list* list){
	listEmpty(list);
	free(list); 
	list = NULL;
}

//头插 
list* listAddNodeHead(list* list,int val){
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->value = val;
	if(list->len==0){
		list->head = list->tail=node;
		node->prev=node->next=NULL;
	}else{
		node->prev = NULL;
		
		node->next = list->head;
		list->head->prev = node; 
		
		list->head = node;
	}
	list->len++;
	return list; 
}
//尾插
list* listAddNodeTail(list* myList,int val){
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->value = val;
	if(myList->len==0){
		myList->head = myList->tail = node;
		node->prev=node->next=NULL; 
	}else{
		node->prev = myList->tail;
		myList->tail->next = node;
		
		node->next=NULL;
		
		myList->tail = node;
	}
	myList->len++;
	return myList;
} 

//插入到指定节点前面或后面 
list* listInsertNode(list* list,listNode* old_node,int val,bool after){
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->value = val;
	if(after){
		
		node->prev = old_node;
		node->next = old_node->next; 
		if(list->tail==old_node){
			list->tail = node;	
		}
	}else{
		
		node->next = old_node;
		node->prev = old_node->prev;
		if(list->head==old_node){
			list->head = node;
		}	
	}
	
	if(node->prev!=NULL){
		node->prev->next = node;
	}
	if(node->next!=NULL){
		node->next->prev = node;
	}
	list->len++;
	return list;
}

//删除指定节点 
void listDelNode(list* list,listNode* node){
	if(node->prev)
		node->prev->next = node->next; 
	else //是头节点 
		list->head = node->next;
	
	if(node->next) //如果不是尾节点
		node->next->prev = node->prev;
	else
		list->tail = node->prev; 
	free(node);
	node = NULL;
	list->len--;
} 

//链表的复制
list* listCopy(list* old_list){
	
	list* new_list = listCreate();
		
	listNode* node = old_list->head;
	while(node){
		listAddNodeTail(new_list,node->value);
		node = node->next;
	} 
	//listRelease(old_list);
	return new_list;
} 

//根据值查找节点 
listNode* listSearchKey(list* myList,int val){
	listNode* node = myList->head;
	while(node && node->value!=val)
		node = node->next;
	if(node)
		return node;
	else
		return NULL; 
}

//根据索引查找节点 支持倒排序索引 
listNode* listIndex(list* list,int index){
	listNode* node;
	
	if(index<0){
		index = (-index)-1;
		node = list->tail;
		while(index-- && node) node =node->prev; 
	}
	else{
		node = list->head;
		while(index-- && node) node = node->next; 
	}
	return node;
} 
 
//second连接到first
list* listJoin(list* first,list* second){
	if(second->head)
		second->head->prev = first->tail;
	
	if(first->tail)
		first->tail->next = second->head;
	else //first链表是空的
		first->head = second->head;
	
	
	if(second->tail)
		first->tail = second->tail;
	
	
	first->len +=second->len;
	
	second->head = second->tail = NULL;
	second->len = 0;
	
	return first;	
}



void Show_Int_List(list* list){
	listNode* node = list->head;
	while(node){
		cout<<node->value<<endl;
		node = node->next;
	}
		
} 


int main(){
	
	list* myList1 = listCreate();
	for(int i=1;i<=5;i++)
		listAddNodeTail(myList1,i);
	Show_Int_List(myList1);
	cout<<endl;
	
	list* myList2 = listCreate();
	for(int i=6;i<=10;i++)
		listAddNodeTail(myList2,i);
	Show_Int_List(myList2);
	cout<<endl;
	
	listJoin(myList1,myList2);
	Show_Int_List(myList1);
	cout<<endl;
	
	cout<<listIndex(myList1,-2)->value<<endl;
	cout<<endl;
	
	list* myList3=NULL;
	myList3 = listCopy(myList1);
	listAddNodeHead(myList3,99);
	listDelNode(myList3,listSearchKey(myList3,10));
	Show_Int_List(myList3);
	cout<<endl;
	cout<<"len:"<<myList3->len<<endl;
	
	
	
	return 0;
}