线性表是数据结构中比較重要的一种结构。线性表能够用连续存储空间来表示，也能够用链表的形式表示。链式存储结构不要求在逻辑上相邻的元素在物理位置上也相邻，因此他在插入元素和删除元素上具有着得天独厚的优势，可是却失去了顺序存储中可随机存储的长处。

线性链表中每一个元素被存放在一个叫做结点的地方，结点包括一个数据域和一个指针域，数据域存放元素，指针域存放着指向下一个结点的指针。若链表的结点中仅仅包括一个指针域，那么这个链表被称为线性链表或者单链表。有时我们会在第一个结点前加上一个结点，这个结点的数据域能够不存放内容，也能够存放数据元素的个数，指针域指向第一个结点，当头结点的指针域为空时，那么这个链表就为一个空链表。

以下是实现单链表的代码：

首先定义一个结点结构体：包括一个数据域和一个指针域

typedef struct LNode{	int data;	LNode *next;}LNode,*LinkList;

以下来创建一个链表：输入为元素的个数，此链表具有头结点

void createList(LinkList &L,int n) //这里一定要加引用传递{	L=new LNode;	L->next=NULL;	LinkList p=NULL;	for(int i=n;i>0;i--)	{		p=new LNode;		cin>>p->data;		p->next=L->next;		L->next=p;	}}

第一个參数要加引用传递，原因以下会讲到；

以下是关于在某个位置往链表中插入一个元素的代码：

bool listInsert(LinkList L,int i,int e){	LinkList p=L;int j=0;	while(p && j
     
      next;		j++;	}	if(!p||j>i-1) return false;	LinkList s=new LNode;	s->data=e;	s->next=p->next;	p->next=s;	return true;}
     

接下来是获得链表中某个位置上元素的数据的代码：

bool getElem(LinkList L,int i,int &e){	LinkList p=NULL;	p=L->next;	int j=0;	while(j
     
      next;		j++;	}	if(!p||j>i) return false;	e=p->data;	return true;}
     

最后写了測试代码的程序：

void main(){	LNode *p=NULL;	createList(p,5);	int x=0;	cout<<"before inserting: ";	showList(p);	listInsert(p,1,20);	cout<<"after inserting: ";	showList(p);	cout<<"get a value: ";	getElem(p,2,x);	cout<
     
      <
     

当中showlist()为打印链表元素的函数：

void showList(LinkList L){	LinkList p=L->next;	while(p)	{			cout<
     
      data<<" ";		p=p->next;	}	cout<
     

上面说到为什么要加引用传递參数呢？那是由于我们传递的是指针，而指针的地址是在调用函数中申请的，等于给指针赋值了，调用函数结束后，这个地址就销毁了。可是可能有人问那为什么我们传址的函数能够使用指针呢？那是由于我们在调用前这种指针的地址已经存在了。