1.基本資料型別

typedef int LTDatatype;

typedef struct LTNode
{
	LTDatatype data;
	struct LTNode* pre;
	struct LTNode* next;
}LTNode;

2.新建結點

開辟一個結點空間并回傳

LTNode* BuyNewNode()
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	return newnode;
}

3.初始化鏈表

制造哨兵結點

LTNode* ListInit()
{
	LTNode* phead = BuyNewNode();
	assert(phead);
	phead->next = phead;
	phead->pre = phead;
	return phead;
}

4.列印鏈表

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead )
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("plist\n");
}

注意這里回圈的條件，cur！=哨兵結點

5.尾插結點

void ListPushBack(LTNode* phead, LTDatatype x)
{
	assert(phead);
	
	LTNode* newnode = BuyNewNode();
	assert(newnode);
	newnode->data = x;

	LTNode* tail = phead->pre;
	tail->next = newnode;
	newnode->pre = tail;
	newnode->next = phead;
	phead->pre = newnode;
}

6.頭插結點

void ListPushFront(LTNode* phead, LTDatatype x)
{
	assert(phead);

	LTNode* newnode = BuyNewNode();
	assert(newnode);
	newnode->data = x;
	
	LTNode* post = phead->next;

	newnode->pre = phead;
	newnode->next = post;
	phead->next = newnode;
	post->pre = newnode;

}

7.尾刪結點

洗掉結點時，注意哨兵結點的保留

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->pre != phead);

	LTNode* tail = phead->pre;//找到尾結點
	LTNode* pretail = tail->pre;//尾結點的前一個結點
	pretail->next = phead;
	phead->pre = pretail;
	free(tail);
}

8.頭刪結點

仍然注意哨兵結點的保留

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);

	LTNode* post = phead->next;
	LTNode* postPost = phead->next->next;

	phead->next = postPost;
	postPost->pre = phead;
	free(post);

}

9.尋找鏈表結點，回傳地址

遍歷鏈表，滿足條件，回傳地址

LTNode* ListFind(LTNode* phead, LTDatatype x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

10.鏈表插入結點

已知鏈表某結點地址，在其前插入結點

void ListInsert(LTNode* pos, LTDatatype x)
{
	assert(pos);

	LTNode* newnode = BuyNewNode();
	assert(newnode);
	newnode->data = x;

	LTNode* prepos = pos->pre;
	//在prepos和pos之間插入x
	prepos->next = newnode;
	newnode->pre = prepos;
	newnode->next = pos;
	pos->pre = newnode;
}

由此可以將此函式復用于尾插和頭插函式中
尾插復用：

void ListPushBack(LTNode* phead, LTDatatype x)
{
	assert(phead);

	//插入函式在尾插中的復用
	ListInsert(phead, x);
}

頭插復用：

void ListPushFront(LTNode* phead, LTDatatype x)
{
	assert(phead);

	//插入函式在頭插中的復用
	ListInsert(phead->next,x);
}

11.鏈表洗掉結點

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prepos = pos->pre;
	LTNode* postpos = pos->next;
	prepos->next = postpos;
	postpos->pre = prepos;
	free(pos);
}

由此可以將此函式復用于尾刪和頭刪函式中
尾刪復用：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->pre != phead);

	//洗掉函式在尾刪中的復用
	ListErase(phead->pre);
}

頭刪復用：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);

	//洗掉函式在頭刪中的復用
	ListErase(phead->next);
}

12.代碼演示

void test();

int main()
{
	test1();
	return 0;
}

void test1()
{
	LTNode* plist = NULL;
	//初始化
	plist=ListInit();
	//尾插
	printf("尾插1 2 3 4 \n");
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	//尾刪
	printf("尾刪\n");
	ListPopBack(plist);
	ListPrint(plist);
	//頭插
	printf("頭插1 2 3 4 \n");
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPrint(plist);
	//頭刪
	printf("頭刪\n");
	ListPopFront(plist);
	ListPrint(plist);
	//查找
	printf("查找2的位置\n");
	LTNode* pos=ListFind(plist,2);
	printf("2的位置在pos=%p\n", pos);

	//插入
	printf("在2之前插入6\n");
	ListInsert( pos, 6);
	ListPrint(plist);

}

青山不改 綠水長流