优点：
1 空间存储方便，现用现申请
2 插入删除，只针对单一数据，不需要移动大量数据
缺点：
1 读取，插入，删除慢，需要从头查找，时间复杂度均为O(n)
数据结构声明
typedef struct Node{ int data; struct Node * next; }Node; int main(){ ... Node *p = (Node *)malloc(sizeof(Node)); p->data = 1; ... }
链表读取指定位置的元素
void getNode(Node *L,int n,Node *tar){ int i=1; Node *p; p=L->next; while(p && i<n){ p=p->next; i++; } if(!p || i>n) printf("error!"); tar->data=p->data; }
链表整表的删除
链表不能直接删除头结点，此时元素节点仍在使用中。
void clearList(Node *L){ Node *p,*q; p=L->next; while(p){ q=p->next; free(p); p=q; } L->next=NULL; }
链表在指定位置插入节点
int insertNode(Node *L,int n,int num){ int i=1; Node *p = L->next; while( p && i<n-1){ p=p->next; i++; } if(!p || i>n-1) return 0; Node *q = (Node *)malloc(sizeof(Node)); q->data = num; q->next = p->next; p->next = q; return 1; }
链表删除指定位置的节点
int deleteNode(Node *L,int n){ int i=1; Node *p = L->next; Node *q; while( p->next && i<n-1){ p=p->next; i++; } if( !(p->next) || i>n-1) return 0; q=p->next; p->next = q->next; free(q); return 1; }
完整的示例代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct Node{ 5 int data; 6 struct Node * next; 7 }Node; 8 9 void createList(Node * L,int len); 10 void showList(Node *L); 11 void clearList(Node *L); 12 void getNode(Node *L,int n,Node *tar); 13 int insertNode(Node *L,int n,int num); 14 int deleteNode(Node *L,int n); 15 16 int main() 17 { 18 Node *L= (Node *)malloc(sizeof(Node)); 19 20 createList(L,5); 21 showList(L); 22 23 Node *tar= (Node *)malloc(sizeof(Node)); 24 getNode(L,3,tar); 25 printf("the third is:%d\n",tar->data); 26 27 if(insertNode(L,3,0)) 28 showList(L); 29 30 if(deleteNode(L,3)) 31 showList(L); 32 33 clearList(L); 34 showList(L); 35 36 return 0; 37 } 38 39 void createList(Node * L,int len){ 40 int i; 41 Node * p; 42 L->next = NULL; 43 for(i=0;i<len;i++){ 44 p = (Node *)malloc(sizeof(Node)); 45 p->data = 2*i+1; 46 p->next = L->next; 47 L->next = p; 48 } 49 } 50 51 void showList(Node *L){ 52 Node *p = (Node *)malloc(sizeof(Node)); 53 p=L->next; 54 while(p){ 55 printf("%d->",p->data); 56 p=p->next; 57 } 58 printf("null\n"); 59 free(p); 60 } 61 62 void clearList(Node *L){ 63 Node *p,*q; 64 p=L->next; 65 while(p){ 66 q=p->next; 67 free(p); 68 p=q; 69 } 70 L->next=NULL; 71 } 72 73 void getNode(Node *L,int n,Node *tar){ 74 int i=1; 75 Node *p; 76 p=L->next; 77 while(p && i<n){ 78 p=p->next; 79 i++; 80 } 81 if(!p || i>n) 82 printf("error!"); 83 tar->data=p->data; 84 } 85 86 int insertNode(Node *L,int n,int num){ 87 int i=1; 88 Node *p = L->next; 89 while( p && i<n-1){ 90 p=p->next; 91 i++; 92 } 93 if(!p || i>n-1) 94 return 0; 95 Node *q = (Node *)malloc(sizeof(Node)); 96 q->data = num; 97 q->next = p->next; 98 p->next = q; 99 return 1; 100 } 101 102 int deleteNode(Node *L,int n){ 103 int i=1; 104 Node *p = L->next; 105 Node *q; 106 while( p->next && i<n-1){ 107 p=p->next; 108 i++; 109 } 110 if( !(p->next) || i>n-1) 111 return 0; 112 q=p->next; 113 p->next = q->next; 114 free(q); 115 return 1; 116 }