学步园

双向链表是数据结构中最常用的数据组织方式。下面介绍一些常见的操作。

1） 一般会有如下定义：

//struct definition
typedef struct __node list;

struct __node
{
	struct __node *pre;
	struct __node *next;
	void *p_data;
};

这里pre和next分别指向前一个和后一个结点， p_data指向一个任意类型的数据或者一般特定类型的数据。

2）创建一个节点：

list *create()
{
	list *lst = (list*) malloc (sizeof(list));
	if (lst == NULL)
		return NULL;

	lst->pre = NULL;
	lst->next = NULL;
	lst->p_data = NULL;

	return lst;
}

3）追加一个节点：

int add_tail(list *old, list *new)
{
	if (new == NULL)
		return -1;

	list *p;
	for (p = old; p->next != NULL; p = p->next) ;

	p->next = new;
	new->next = NULL;
	new->pre = p;

	return 0;
}

3）在特定节点后插入一个新节点：

int add_node(list *head, void *data0, void *data1)
{
	if (head == NULL)
		return -1;

	int value;
	list *p, *new;

	value = *((int *)data0);

	for (p = head; p->next != NULL; p = p->next)
	{
		if (value == *((int *)p->p_data))
		{
			new = (list *)malloc(sizeof(list));
			if (new != NULL)
			{
				new->p_data = malloc(sizeof(int));
				if (new->p_data != NULL)
				{
					*((int *)(new->p_data)) = *((int *)data1);		
				}
				else
				{
					free(new);
					return -1;
				}
		
				new->pre = p;
				new->next = p->next;
				p->next->pre = new;
				p->next = new;
			}
			else
			{
				return -1;
			}

			break;
		}
	}

	return 0;
}

这里p_data指向的数据类型为int，在data0后插入数据域为data1的节点。

4）删除一个节点：

int del_node(list *head, void *data)
{
	if (head == NULL)
		return -1;
	
	int value;
	list *p, *new;

	value = *((int *)data);
	for (p = head; p->next != NULL; p = p->next)
	{
		if (value == *((int *)p->p_data))
		{
			p->pre->next = p->next;
			p->next->pre = p->pre;
	
			free(p->p_data);
			free(p);

			break;
		}
	}

	return 0;
}

删除第一个数据域为data的节点。

以上是链表的定义及一些常用的操作，下一篇继续介绍一些操作。