链表的定义：
链表链表有一系列不必再内存中连续的结构组成，不需要使用地址连续的存储单元。它是通过“链”来建立逻辑关系的，因此在对链表进行插入，删除操作时不需要移动元素，而只需要修改指针即可。
链表分类：按是否包含指向前继的指针可分为单链表和双向链表；按是否成环状可以分为循环链表和非循环链表。
由于连表示离散的分布在存储空间的，因此链表是非随机存取的，只能从某个特定节点开始遍历一次查找。
通常为方便操作，在链表第一个节点前附加一个头节点，头节点的指针与指向链表的第一个元素节点。
链表的实现与常见算法
单链表
　　每个结构含有表元素和指向包含该元素后继的结构的指针。除了头节点，每一个结点都有唯一的前继。除最后一个结点，每一个结点都有一个后继。


插入：


删除：


双向链表
双向链表与单链表的不同之处在于，双向链表的每个结点含有两个指针域，其中一个指向直接前继，一个指向直接后继。这样双向链表可以沿两个方向进行遍历；


插入：


删除：



struct LNode {
	ElementType e;
	PtrToLNode Next;
};

typedef struct LNode *PtrToLNode;
typedef PtrToLNode List;
List List_Init(void)
{
	List L = (List)malloc(sizeof(LNode));
	L->Next = NULL;
	return L;
}

int List_IsEmpty(List L)
{
	if (L->Next = NULL)
		return 1;
	else
		return 0;
}

void List_Print(List L)
{
	PtrToLNode p = L->Next;
	while (p){
		printf("%d\t", p->e);
		p = p->Next;
	}
	printf("\n");
}

void List_Pre_Create(List L)//头插法建立单链表
{
	ElementType x;
	scanf("%d", &x);
	while (x != 9999) {
		PtrToLNode p = (PtrToLNode)malloc(sizeof(LNode));
		p->e = x;
		p->Next = L->Next;
		L->Next = p;
		scanf("%d", &x);
	}
}

void List_Post_Create(List L)//尾差法建立单链表
{
	ElementType x;
	PtrToLNode p, r = L;
	scanf("%d", &x);
	while (x != 9999) {
		p = (PtrToLNode)malloc(sizeof(LNode));
		p->e = x;
		r->Next = p;
		r = p;
		scanf("%d", &x);
	}
	r->Next = NULL;
}

PtrToLNode List_FindPre(List L, PtrToLNode r)//返回结点r的直接前继
{
	PtrToLNode pre = L, p = pre->Next;
	while (p != r) {
		pre = p;
		p = p->Next;
	}
	return pre;
}

int List_Length(List L)//求链表长度
{
	int Length = 0;
	PtrToLNode p = L->Next;
	while (p) {
		++Length;
		p = p->Next;
	}
	return Length;
}

void List_Insert(List L, Position p, ElementType x)//在结点p处插入新节点
{
	PtrToLNode pre = List_FindPre(L, p), s;
	s = (PtrToLNode)malloc(sizeof(LNode));
	s->e = x;
	s->Next = p;
	pre->Next = s;
}

PtrToLNode List_FindMid(List L)//返回中间元素结点
{
	PtrToLNode p, r;
	p = r = L->Next;
	while (r->Next != NULL && r->Next->Next != NULL){
		p = p->Next;
		r = r->Next->Next;
	}
	printf("%d\n", p->e);
	return p;
}

void List_Delete(List L, ElementType x)//删除节点
{
	PtrToLNode pre = L, p = L->Next, temp;
	while (p){
		if (p->e != x) {
			pre = p;
			p = p->Next;
		}
		else{
			temp = p->Next;
			pre->Next = temp;
			free(p);
			p = temp;
		}
	}
}

void List_DeleteRepeat(List L)//删除有序链表中重复元素的结点
{
	PtrToLNode pre = L->Next, p = pre->Next, temp;
	while (p){
		if (pre->e == p->e) {
			temp = p->Next;
			pre->Next = temp;
			free(p);
			p = temp;
		}
		else {
			pre = p;
			p = p->Next;
		}
	}
}

PtrToLNode List_Last_K(List L, int k)//返回倒数第K个结点
{
	PtrToLNode p, r;
	p = r = L;
	if (k > List_Length(L)) {
		printf("The k is Bigger Than L's Length!\n");
		return NULL;
	}
	for (int i = 0; i < k; ++i)
		r = r->Next;
	while (r){
		r = r->Next;
		p = p->Next;
	}
	printf("%d\n", p->e);
	return p;
}
/*若两单链表有公共结点，则从起始公共结点至尾结点两者均相同，因此将两链表尾部对齐，开始比较第一个相同结点即为起始公共结点*/
PtrToLNode List_CommonNode(List L1, List L2)//返回两单链表的公共起始节点
{
	int Length1, Length2, dist;
	PtrToLNode longlist, shortlist;
	Length1 = List_Length(L1);
	Length2 = List_Length(L2);
	if (Length1 > Length2) {
		longlist = L1->Next;
		shortlist = L2->Next;
		dist = Length1 - Length2;
	}
	else {
		longlist = L2->Next;
		shortlist = L1->Next;
		dist = Length2 - Length1;
	}
	while (dist--)
		longlist = longlist->Next;
	while(longlist && longlist->e != shortlist->e){
		longlist = longlist->Next;
		shortlist = shortlist->Next;
	}
	PtrToLNode p = longlist;
	while (p) {
		printf("%d\n", p->e);
		p = p->Next;
	}
	return longlist;
}

void List_Reverse(List L)//
{
	PtrToLNode pre, p, r;
	pre = L;
	p = pre->Next;
	r = p->Next;
	p->Next = NULL;//将逆置后的p将成为尾结点，将其指针域置空
	while (r) {
		pre = p;
		p = r;
		r = r->Next;//遍历链表
		p->Next = pre;//逆置
	}
	L->Next = p;//p结点将成为你逆置后的第一个节点，将头节点指向该节点
}
</pre><pre name="code" class="cpp"><pre name="code" class="cpp">void List_Reverse1(List L)//利用头插法逆置链表
{
	PtrToLNode p, r;
	p = L->Next;
	L->Next = NULL;
	while (p) {
		r = p->Next;
		p->Next = L->Next;
		L->Next = p;
		p = r;
	}
}


List List_Reverse1(List L, int m, int n)//逆置第m个结点至第n个结点结点
{
	List prefirst, first, p, r;
	prefirst = L;
	first = p = L->Next;
	for (int i = 1; i != m; ++i) {
		prefirst = p;
		p = p->Next;
	}//prefirst指向第m-1个结点
	first = p;//first指向第m个结点
	for (int i = m; i <= n; ++i) {
		r = p->Next;
		p->Next = prefirst->Next;
		prefirst->Next = p;
		p = r;
	}//利用头插法将m至n结点逆置
	first->Next = p;//将first的指针域指向第n+1个结点
	return L;
}

双链表

/*
* Created by Dev-c++5.11
* @author: Teresa0312
* @date: 2017-10-05
* @description: 顺序表操作
*/

#include <stdio.h>
#include <stdlib.h>
/*函数状态码*/
#define TRUE 1	//成功
#define OK 1
#define FALSE 0	//失败 
#define ERROR 0	//错误 
#define INFEASIBLE -1	//不可行的
#define OVERFLOW -2 	//溢出

#define LIST_INIT_SIZE	100	//线性表存储空间的初始分配量
#define LISTINCREMENT	10	//线性表存储空间的增量 

typedef int ElemType; //基本数据类型
typedef int Status;	//函数的返回值类型 

/*线性表的动态分配顺序存储结构*/
typedef struct{
	ElemType *elem;	//存储空间基址 
	int length;	//当前长度
	int listsize;	//当前分配的存储容量 以sizeof(ElemType)为单位
}SqList;


//初始化线性表L
Status ListInit(SqList *L){
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));		//分配LIST_INIT_SIZE个ElemType的空间
	if (!L->elem){
		exit(OVERFLOW);	//存储分配失败则退出程序
	}
	L->length = 0;		//空表长度为0
	L->listsize = LIST_INIT_SIZE;	//初试存储容量
	return TRUE;
}

//销毁线性表L
Status DestroyList(SqList *L){
	free(L->elem);		//先释放内存
	L->elem = NULL;	//再赋值为NULL
	L->length = 0;		
	L->listsize = 0;	
	return OK;
};

//将L置为空表
Status ClearList(SqList *L){
	L->length = 0;		//置为空表长度为0
	return OK;
}

//若L为空表则返回TRUE 否则返回 FALSE
Status ListEmpty(SqList L){
	if (L.length == 0)
		return TRUE;
	else
		return FALSE;
}

//返回L中数据元素的个数
Status ListLength(SqList L){
	return L.length;
}

//用e返回L中第i个数据元素的值
Status  GetElem(SqList L, int i, ElemType * e){
	if (i <= L.length){		//如果i小于线性表的长度
		*e = *(L.elem + i - 1);	//返回第i个数据元素的值
		return *e;
	}
	else		//否则 返回FALSE
		return FALSE;
}

//返回 L中第一个与e满足关系compare()的数据元素的位序 若不存在 则返回0
Status LocateElem(SqList L, ElemType e, Status (*compare)(ElemType,ElemType)){
	ElemType *p=&e;	
	int i=0;
	while (i <= L.length && !(*compare)(*p,e)){
		//当i小于等于线性表的长度 并且 没有找到与e满足compare()关系的数据元素时 执行循环
		i++;
		p+=sizeof(ElemType);
	}
	if (i < L.length){
		//当i小于线性表的长度时 说明找到了
		return *p;
	}
	else
		return FALSE;	//否则 没有找到

}

//若cur_e是L的数据元素 且不是第一个 则用pre_e返回它的前驱 否则操作失败 pre_e无定义
Status PriorElem(SqList L, ElemType cur_e, ElemType * pre_e){
	ElemType *p=L.elem;
	int i = 1;
	if (*p == cur_e){	//如果是第一个数据元素 则不可行
		printf("它没有前驱 不可行");
		return INFEASIBLE;
	}
	else{
		while (i < L.length && *p != cur_e){
			//从第一个元素开始 与cur_e比较 直至相等或L的最后
			i++;
			p++;
		}
		if (i > L.length)		//没找到 返回INFEASIBLE
			return INFEASIBLE;
		else{
			*pre_e = *(p - 1);		//若找到 将后一个元素赋给pre_e
			return OK;
		}
	}
}

///若cur_e是L的数据元素 且不是最后一个 则用next_e返回它的前驱 否则操作失败 next_e无定义
Status NextElem(SqList L, ElemType cur_e, ElemType * next_e){
	ElemType *p = L.elem;
	int i = 1;
	while (i <= L.length && *p != cur_e){
		//从第一个元素开始 与cur_e比较 直至相等或L的最后
		i++;
		p++;
	}
	if (i >= L.length)		//没找到 返回INFEASIBLE
		return INFEASIBLE;
	else{
		*next_e = *(p + 1);		//若找到 将后一个元素赋给next_e
		return OK;
	}
}

//在L中的第i个位置之前插入新的数据元素e,L的长度加1
Status ListInsert(SqList *L, int i, ElemType e){
	ElemType *newbase, *q, *p;
	if (i <1 || i>L->length + 1)      //判断i是否在顺序表的长度之内          
		return FALSE; 
	if (L->length >= L->listsize)
	{	///如果L.length已经达到或超出设定值，需要扩容 
		newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) *sizeof(ElemType));
		//重新分配空间 给newbase动态分配一个长度为LISTINCREMENT的新空间d  
		if (!newbase)
			exit(OVERFLOW);	//如果分配失败 返回错误
		L->elem = newbase;      //新基址  
		L->listsize += LISTINCREMENT;  //增加存储容量  
	}
	q = L->elem + i - 1;    //q为插入位置  
	for (p = (*L).elem + (*L).length - 1; p >= q; --p) //插入位置及之后的元素右移 
		*(p + 1) = *p;	//将原来顺序表最后一个位置数据的地址分配给p，然后从后往前依次将数据向后移动一位  
	*q = e; //插入e
	(*L).length++; // 表长增1 
	return OK;
}

//删除L中的第i个元素 并用e返回其值 L的长度减1
Status ListDelete(SqList *L, int i, ElemType * e){
	ElemType *q, *p;
	if (i <1 || i>L->length)		//判断i是否在顺序表的长度之内  
  		return ERROR;
	p = L->elem + L->length - 1;		//p指向最后一个数据元素
	q = L->elem + i - 1;    //q为删除位置  
	for (q; q < p; q++) //删除位置及之后的元素左移 
		*q = *(q + 1);
	--(*L).length; // 表长减1
	return OK;
}

//对L的每一个元素调用函数visit 一旦visit()失败 则操作失败
Status ListTraverse(SqList L, void (*visit)(ElemType *)){
	ElemType *ptr;	//遍历数组
	ptr = L.elem;
	ElemType i = 0;
	for (i = 0; i < L.length; i++)
		visit(ptr + i);		//遍历数组
	printf("\n");
	return OK;
}

//若数据元素a与b相等则返回TRUE 否则返回 FALSE
Status compare(ElemType a, ElemType b){
	if (a == b){
		return TRUE;	
	}
	else
		return FALSE;
}
//输出数据元素
void visit(ElemType *e){
	printf("%c ", *e);
}


int main(){
	SqList a;
	ElemType e;
	int i = 0;
	ListInit(&a);
	printf("顺序表创建成功\n"); 
	for (i = 1; i <=26; i++)
		ListInsert(&a, i,  97+i-1);
	printf("初始化顺序表完成\n"); 
	printf("输出顺序表\n");
	ListTraverse(a, visit);
	printf("输出第3个元素的前驱");
	PriorElem(a, 'c', &e);
	printf("%c\n",e);
	printf("输出第3个元素的后继");
	NextElem(a, 'c', &e);
	printf("%c\n",e);
	printf("输出与t相等的元素");
	printf("%d\n",LocateElem(a,'t',compare));
	if(ListDelete(&a,6,&e))
	printf("删除%c成功\n",'a'+6-1); 
	printf("输出顺序表\n");
	ListTraverse(a, visit);
}

#include <stdio.h>
#include <stdlib.h>
#define name_to_str(name_)  (#name_)
/**<  定义结点及结构体指针，结构体指针linklist为链表头结点指针*/
typedef struct LNode{
    int data;
    struct LNode* next;
}LNode,*LinkList;//结构体指针
/**< 初始化链表 */
LNode* Init_LL()
{
    LinkList p=(LNode*)malloc(sizeof(LNode));
    p->data=NULL;
    p->next=NULL;
    return p;
}
/**< 在第pos个结点之前插入一个DATA为Val的新节点 */
void Insert_LL(LinkList pLL,int pos,int Val)
{
    LNode* P=pLL;
    LNode* A=Init_LL();//不初始化结点不能使用，malloc相关。
    A->data=Val;
    int i;
        for(i=0;i<pos-1;i++)
    {if(P)
        P=P->next;
    else
        {
            printf("位置非法");
            exit(-1);}
        }
    A->next=P->next;
    P->next=A;
}
/**< 删除结点,pos之前 */
void Delete_LL(LinkList pLL,int pos)
{
    int i;
    LinkList q,p=pLL;
    for(i=0;i<pos-1;i++)
        p=p->next;
    q=p->next;
    p->next=q->next;
    free(q);
}
/**< 求直接前驱 */
LNode* PriorElment_LL(LinkList pLL,int Data)
{
    LinkList p=pLL;
    while(p->next->data!=Data)
        p=p->next;
        printf("%d_prior_element_data_is_%d",Data,p->data);
        return p;
}
/**< 求直接后继 */
LNode* NextElment_LL(LinkList pLL,int Data)
{
    LinkList p=pLL;
    while(p->data!=Data)
        p=p->next;
        printf("%d_next_element_data_is_%d",Data,p->data);
        return p;
}
/**<  返回第POS个数据的值*/
int GetElement_LL(LinkList pLL,int pos)
{
    LinkList p=pLL;
    int i;
    for(i=0;i<pos;i++)
        p=p->next;
    printf("the %dth element is %d",pos,p->data);
    return p->data;
}
/**< 泡排 */
void BubbleSort_LL(LinkList pLL)
{
    LinkList p=pLL,q;
    int cnt=0,i,j,temp;
    while(p->next!=NULL)
    {
        cnt++;
        p=p->next;
    }
    //printf("cnt=%d",cnt);
    q=pLL->next;
        for(i=0;i<cnt-1;i++)
{
    p=q;
        for(j=0;j<cnt-i-1;j++)
    {
        if(p->data<p->next->data)
        {
            temp=p->data;
            p->data=p->next->data;
            p->next->data=temp;
            //printf("比较%d?=%dexchange\n",p->data,p->next->data);///非常奇怪，总是大数小数exchange
            p=p->next;
        }
        else
        {
            //printf("比较%d?=%dunchange\n",p->data,p->next->data);
            p=p->next;}


    }
    //printf("当前循环完成\n");
}


        Printf_LL(pLL);


}
/**< 合并有序链表 */
LinkList Add_LL(LinkList p,LinkList q)
{
    LinkList a=p->next,b=q->next;
    LinkList c=Init_LL();
    LinkList L=c;
    while(a&&b)
{
    if (a->data>=b->data)
        {
         //   printf("1   %d,%d\n",a->data,b->data);
            c->next=a;
            a=a->next;


        }
    else
        {
        //    printf("2   %d,%d\n",a->data,b->data);
            c->next=b;
            b=b->next;


        }
   //     printf("CDATA=%d\n",c->data);
    c=c->next;
    c->next=NULL;
}
if (a==NULL)
    c->next=b;
else c->next=a;
printf("合并有序链表结果为：\n");
Printf_LL(L);


}
/**< 打印链表 */
void Printf_LL(LinkList pLL)
{
    LNode* p=pLL;
    int i=1;
    printf("打印链表结果为：");
    do{
        p=p->next;
        printf("linklist[%d]=%d\t",i,p->data);
        i++;
    }while(p->next!=NULL);
    printf("\n\n");
}
/**< 测试ADT */
int main()
{
    LinkList p=Init_LL();
    Insert_LL(p,1,6);
    Insert_LL(p,2,8);
    Insert_LL(p,3,4);
    Insert_LL(p,3,3);
    Insert_LL(p,2,1);
    Insert_LL(p,4,9);
    Printf_LL(p);
    LinkList q=Init_LL();
    Insert_LL(q,1,2);
    Insert_LL(q,2,5);
    Insert_LL(q,3,7);
    Insert_LL(q,3,3);
    Insert_LL(q,2,11);
    Insert_LL(q,3,20);
    Insert_LL(q,1,12);
    Printf_LL(q);
    BubbleSort_LL(p);
    BubbleSort_LL(q);
    Add_LL(p,q);
    return 0;
}

链表ADT
自己打的单链表
希望代码对大家有帮助哈哈，很全。

基本实现了应该有的功能
1.判断链表是否为空
2.判断链表是否为满
3.节点数量
4.链表的遍历
5.链表节点的替换
6.链表节点的寻找
7.链表节点的插入
8.链表节点的添加



#define true 1
#define false 0
#include <stdio.h>
#include <stdlib.h>
struct list 
  {int data;
   struct list * next; 
  }; 
typedef struct list List;  
int ListIsEmpty( List * head);
unsigned int ListItemCount( List * head);
void Traverse( List * head);
void Replace( List **ptr,int a,List * target);
List * SeekItem( List * head,int a);
bool InsertItem( List *head,int a,List * target);
int InsertHeadItem(List ** ptr,List * target);
List * AddItem( List * head);
int main(void)
{
}
int ListIsEmpty( List * head)
{
	if(head==NULL)
	return true;
	else return false;
 } 
unsigned int ListItemCount( List * head)
{
	unsigned int count=0;
	List * p=head;
	while(p!=NULL){
		++count;
		p=p->next;
	}
	return count;
}
void Traverse( List * head)
{
	int count = 0;
	List * p=head;
	while(p!=NULL){
		++count;
		printf("%d%10d\n",count,p->data);
		p=p->next;
	}
}
void Replace( List **ptr,int a,List * target)//Replace(ptr,a,target);List **ptr   为了能替换第一个节点 ，需要改变头指针的值 
{
	List * p=*ptr;
	List * pr=p;
	if(*ptr==NULL) {
		printf("nothing!");
		exit(0); 
	}
	while(p!=NULL&&p->data!=a){
		pr=p;
		p=p->next;
	}
	if(p==NULL){
		printf("not found!");
		exit(1);
	}
	
	if(p!=NULL){
		if(*ptr==p){
			target->next=p->next;
			*ptr=target;
			free(p);
		}
        else{
		
			target->next=p->next;
		    pr->next=target;
		    free(p);
         }
		
	}
}
	

List * SeekItem( List * head,int a)
{
	int count=0;
	List * p,* pr;
	p=head;
	pr=p;
	if(head==NULL){
		printf("nothing!");
		exit(0);
	}
	while(p!=NULL){
		count++;
		pr=p;
		if(p->data==a){
			printf("find it , it's %d\n",count);
			return p;
		}
		p=p->next;
	}
	if(p=NULL){
		printf("not found!");
		return NULL;
	}
}
bool InsertItem( List * head,int a,List * target)
{
	List * p;
	p=SeekItem(head,a);
	if(p==NULL){
		printf("not found !");
		return false;
	}
	target->next=p->next;
	p->next=target;
	return true;
}
int InsertHeadItem(List ** ptr,List * target)
{
	target->next=*ptr;
	*ptr=target;
	return true;
}
List *AddItem( List * head)
{
	List * pr=head;
	List * p=NULL;
	p=(List *)malloc(sizeof(List));
	if(p==NULL){
		printf("can't' malloc!");
		
	}
	p->next=NULL;
	printf("please input data :");
	scanf("%d",&p->data);
	if(head==NULL){
		head=p;
		
	}
	else{
	
      while(pr->next!=NULL){
		pr=pr->next;
		printf("text!\n");
	  }
	  pr->next=p;
	  
    }
    Traverse(head);
	return head;
}

原创 转载注明出处