一、基本概念

带头结点和不带头结点的单链表

带头结点的单链表，头指针head指向头结点，头结点的值域不包含任何信息，从头结点之后的结点开始存储信息。

头指针head不等于NULL，head->next等于NULL时，链表为空。



 

单链表结点定义

typedef struct LNode{

    int data;   //data存放结点数据域

   struct LNode *next;    //指向后继结点的指针

}LNode;  //定义单链表结点类型

引入头结点的好处：（1）无论链表是否为空，头指针总指向头结点的非空指针，（2）开始结点的位置存放在头结点的指针域中，所以链表的第一个位置上的操作和其他位置一致，方便

1. 建立单链表

（1）头插法

从一个空表开始，生成新结点，将读到的数据存放到新结点的数据域，然后将新结点插入到当前两边的表头，即头结点之后

（头插法生成的链表中结点的次序和输入数据的顺序不一致）



关键代码：

LNode *s;int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL;                  //初始链表为空
/*....*/
s=(LNode)malloc(sizeof(LNode));  //创建新结点
s->data=x;
s->next=L->next;
L->next=s;                        //将新结点插入表中，L尾头指针


（2）尾插法

将新结点插入到当前链表的表尾，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。



int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s,*r=L;  //r为表尾指针
/***/
while(x!=maxSize){
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;                  //r指向新的表尾结点
}
r->next=NULL;      //尾节点置空
return L;

 2.按序号查找结点值（O（n））

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL；

LNode *GetElem(LinkList L,int i){
    int j=1;          //计数，初始为1
    LNode *p=L->next;   //头结点指针赋给p
    if(i==0)
        return L;    //若i等于0，返回头结点
    if(i<1)
        return NULL; //若i无效，返回NULL
    while(p&&j<i){  //从第1个结点查找第i个结点
        p=p->next;
        j++;
}
return p;
}

3.按值查找（O（n））

从单链表第一个结点开始，由前往后依次比较表中个结点数据域的值，若某个结点数据域的值等于给定值e,则返回该结点指针；若整个单链表无值相等的结点，则返回NULL；

LNode *Locate(LinkList L,ElemType e){
        LNode *p=L->next;
        while(p!=NULL &&p->data!=e) //从第1个结点开始查找data域为e的结点
            p=p->next;    

        return p;    //找到后返回该结点指针，否则返回NULL
}

4.插入（O（n））

要把x插入到第i个位置，先检查位置是否合法，然后找到待插入位置的前驱结点，即第i-1个结点，再往其后插入新结点

步骤（1）调用序号查找算法GetElem  查找第i-1个结点。假设返回的第i-1个结点为*p

          (2)令新结点*s的指针域指向*p的后继结点，

           (3)再令结点*P的指针域指向新插入的结点*s

p=GetElem(L,i-1);//查找插入为止的前驱结点
s->next=p->next;   //图中1
p->next=s;         //图中2

 

5.删除（O（n））

要删除第i个结点。先检查删除位置的合法性，然后查找表中第i-1个位置，即被删除结点的前驱结点，再将其删除

假设结点*p为找到的被删除结点的前驱结点，为实现这一操作的逻辑关系的变化，仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点



 

p=GetElem(L,i-1);      //查找删除位置的前驱结点
q=p->next;              //令q指向被删除结点
p->next=q->next;            //将*q结点从链中断开
free(q);                  //释放结点的存储空间

 拓展删除指定结点：

先从表头结点开始顺序找到其前驱结点，然后执行删除

p=p->netx;   //令q指向*p的后继结点

p->data=p->next->data;    //和后继结点交换数据域

p->next=q->next;       //将*q结点从链中断开

free(q)

6.求表长操作

实质为计算数据结点（不含头结点）的个数，需要从第一个开始遍历全部结点。

*p=first->link;
int count=0;
while(p!=NULL){
    p->link;count++;
}
return count;

 

#include <stdio.h>
#include <stdlib.h>
//头插法
#define SIZE 5

#define ERROR 1
#define OK     0

/* 数据元素类型 */
typedef int ListType;

/* 单链表结点定义 */
typedef struct LNode
{
 ListType data;      // 数据域
 struct LNode *next; // 指针域，指向直接后继元素
}LNode;

/* 函数的声明 */
LNode *HeadCreateList(void);// 使用头插法创建一个单链表
LNode *TailCreateList(void);// 使用尾插法创建一个单链表
void PrintfList(LNode *L);  // 打印输出链表



int main(void)
{
 LNode *L1 = NULL;
 LNode *L2 = NULL; 
 
 /* 使用头插法创建单链表 */
 L1 = HeadCreateList();
 printf("头插法创建的链表为：");
 PrintfList(L1);
 return 0;
}


LNode *HeadCreateList(void)//头插法 
{
 int i;
 LNode *L;  // 头结点
 LNode *s;  // 新结点
 L->next = NULL;  // 此时链表为空
 // 创建链表
 for (i = 0; i < 5; i++)
 {
   // 创建新结点
   s = (LNode*)malloc(sizeof(LNode));
   s->data = i;
   // 使用头插法把新元素插入到链表中
   s->next = L->next;  // 新结点的next指针指向头结点
   L->next = s;    // 头结点的next指针指向新结点
 }
 
 return L;
}



void PrintfList(LNode *L)
{
 LNode *temp = L;
 
 while(temp->next)
 {
   temp = temp->next;
   printf("%d ",temp->data);
 }
 printf("\n\n");
}

 

创建单链表
关于数据结构的入门，就是从顺序表和单链表开始。

我们不讲顺序表，直接从单链表开始我们的数据结构和算法的学习之路。
单链表就是一种特殊的结构体组合而成的数据结构，关于单链表的创建方法有很多种，但都大同小异。

正如这幅图中所表示的那样，单链表就是由可能不连续的数据所组合而成的数据结构。 其中每个数据分为两部分，一部分是数据存储的位置，称为数据域，另外指针所存储的地方，称为指针域。
typedef struct Node {
	int data;                    // 存储链表数据
	struct Node *next;     		//  存储结点的地址
}LNode,*Linklist;

在进入创建链表之前，我们先写好主函数的用来输出的输出函数。
void Illustrate(Linklist head) {
	Linklist tem = head;                 //  将头指针的地址赋给临时的指针
	while (tem->next != NULL) {       //  指向最后一个结点的指针域时会停止
		tem = tem->next;               //  结点不断向后移动
		printf("%d\n", tem->data);
	}
}

int main() {
	Linklist head = NULL;            //  链表的头指针
	head = Creat_list(head);        //  创建链表
	Illustrate(head);               //  输出每个结点的数据域
	system("pause");
	return 0;
}

头插法创建单链表

头插法代码：
Linklist Creat_list(Linklist head) {
	head = (Linklist)malloc(sizeof(Lnode));      //  为头指针开辟内存空间
	Lnode *node = NULL;                    //  定义新结点
	int count = 0;                          //  创建结点的个数
	head->next = NULL;              
	node = head->next;              	//  将最后一个结点的指针域永远保持为NULL
	printf("Input the node number: ");
	scanf("%d", &count);
	for (int i = 0; i < count; i++) {
		node = (Linklist)malloc(sizeof(Lnode));     //  为新结点开辟内存空间
		node->data = i;               //  为新结点的数据域赋值
		node->next = head->next;          //  将头指针所指向的下一个结点的地址，赋给新创建结点的next 
		head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点
	}
	return head;
}

头插法创建链表的根本在于深刻理解最后两条语句
	node->next = head->next;          //  将头指针所指向的下一个结点的地址，赋给新创建结点的next 
	head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点

创建第一个结点
执行第一次循环时，第一次从堆中开辟一块内存空间给node，此时需要做的是将第一个结点与 head 连接起来。而我们前面已经说过，单链表的最后一个结点指向的是 NULL。
因此插入第一个结点时，我们需要将头指针指向的 next 赋给新创建的结点的 next ， 这样第一个插入的结点的 next 指向的就是 NULL。 接着，我们将数据域，也就是 node 的地址赋给 head->next， 这时 head->next 指向的就是新创建的 node的地址。而 node 指向的就是 NULL。
接着我们创建第二个结点
因为使用的头插法，因此新开辟的内存空间需要插入 头指针所指向的下一个地址，也就是新开辟的 node 需要插入 上一个 node 和 head  之间。 第一个结点创建之后，head->next 的地址是 第一个 node 的地址。 而我们申请到新的一块存储区域后，需要将 node->next 指向 上一个结点的首地址， 而新node 的地址则赋给 head->next。 因此也就是 node->next = head->next 。

这样便将第一个结点的地址赋给了新创建地址的 next 所指向的地址。后两个结点就连接起来。
接下来再将头结点的 next 所指向的地址赋为 新创建 node 的地址。 head->next = node ，这样就将头结点与新创建的结点连接了起来。  此时最后一个结点，也就是第一次创建的结点的数据域为0，指针域为 NULL。
创建更多的结点也就不难理解。

执行一次：


会发现，头插法创建链表时候，就相当于后来居上。 后面的结点不断往前插，而最后创建的结点在第一个结点处， 第一个创建的结点变成了尾结点。
尾插法创建单链表

尾插法代码：
Linklist Creat_list(Linklist head) {
	head = (Linklist)malloc(sizeof(Lnode));          //  为头指针开辟内存空间
	Linklist node = NULL;           //  定义结点
	Linklist end = NULL;            //  定义尾结点
	head->next = NULL;              //  初始化头结点指向的下一个地址为 NULL
	end = head;                     //  未创建其余结点之前，只有一个头结点
	int count = 0 ;                 //  结点个数
	printf("Input node number: ");
	scanf("%d", &count);
	for (int i = 0; i < count; i++) {
		node = (Linklist)malloc(sizeof(Lnode));          //  为新结点开辟新内存
		node->data = i;                                  //  新结点的数据域赋值
		end->next = node;                      		
		end = node;
	}
	end->next = NULL;
}

尾插法深刻理解：
end->next = node;                      		
end = node;

尾插法创建第一个结点
刚开始为头结点开辟内存空间，因为此时除过头结点没有新的结点的建立，接着将头结点的指针域 head->next  的地址赋为 NULL。因此此时，整个链表只有一个头结点有效，因此 head此时既是头结点，又是尾结点。因此将头结点的地址赋给尾结点 end  因此：end = head。  此时end 就是 head, head 就是 end。 end->next 也自然指向的是 NULL。
尾插法创建第二个结点
创建完第一个结点之后，我们入手创建第二个结点。 第一个结点，end 和 head 共用一块内存空间。现在从堆中心开辟出一块内存给 node，将 node 的数据域赋值后，此时 end 中存储的地址是 head 的地址。此时，end->next  代表的是头结点的指针域，因此 end->next = node 代表的就是将上一个，也就是新开辟的 node 的地址赋给 head 的下一个结点地址。
此时，end->next 的地址是新创建的 node 的地址，而此时 end 的地址还是 head 的地址。 因此 end = node ,这条作用就是将新建的结点 node 的地址赋给尾结点 end。 此时 end 的地址不再是头结点，而是新建的结点 node。
一句话，相当于不断开创新的结点，然后不断将新的结点的地址当做尾结点。尾结点不断后移，而新创的结点时按照创建的先后顺序而连接的。先来新到。
尾插法创建单链表，结点创建完毕
最后，当结点创建完毕，最后不会有新的结点来替换 end ，因此最后需要加上一条 end->next = NULL。将尾指针的指向为 NULL。
创建更多结点也自然容易理解了一些。
执行一次：


总结
由上面的例子以及比较，我们可以看见：

头插法相对简便，但插入的数据与插入的顺序相反；
尾插法操作相对复杂，但插入的数据与插入顺序相同。

两种创建的方法各有千秋，根据实际情况选择不同的方法。
关于链表的相关其他操作，请浏览相关文档。

无环单链表+有环单链表or有环单链表+无环单链表

判断相交

必定不相交

Java内部也有自己的链表--LinkedList，但是我们今天不是讨论LinkedList，而是自己来实现一个单链表，包括简单的增删查改：

		
单链表的结构
		
单链表的基本操作
		
虚拟头结点的使用
	
整个类的设计如下：
public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;			//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
}

单链表的结构

	一种链式存取的数据结构，单链表中的数据是以结点的形式存在，每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的，这也是为什么根据索引无法像数组那样直接就能查询到数据元素。
[单链表结构图]
链表存储的结点
private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
}

链表的基本操作
包括链表的增删查改，以及判别某结点是否存在链表中
链表结点的增加

进行结点的添加的时候，是根据索引来进行操作的，由于成员变量size记录了当前链表的元素个数，进行某个索引位置的结点插入就会很方便了。先找到该目标索引的前一个结点，记录为pre，把要插入的结点node的下一个结点node.next指向pre的下一个结点pre.next；再把pre.next指向node结点。如果先进行pre.next指向要插入的结点，再进行node.next指向pre.next的话，无疑是要插入的结点自己指向了自己，无法连接上整个链表，在链表的操作中，有时候顺序的执行会带来不一样的结果。
//链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		//this.head = new Node(e,head);等价上述代码
		this.size++;
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
	//向链表中间插入元素
	public void add(T t,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
		if (index == 0){
			this.addFirst(t);
			return;
		}
		Node preNode = this.head;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index-1; i++){
			preNode = preNode.next;
		}
		Node node = new Node(t);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
	}

链表结点的删除
//删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur != null && cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}


在进行链表的结点删除时候，要分情况讨论：
当要删除的结点位于头结点的时候：如下图要删除的元素1的结点位于头结点，先进行while判断头结点是否为null且判断该结点的元素是否为要删除的元素，如果是把head指向head.next即可，直接跳过头结点，直到头结点不是要删除的元素就结束循环。
[要删除的元素1位于头结点]
当要删除的结点不在头结点的时候：如下图删除元素为3的结点，由于上面已经判断了头结点不是要删除的元素，所以我们从头结点的下一个结点开始循环，即cur.next，当cur.next是要被删除的元素时，直接cur.next = curr.next.next就能直接跳过cur.next，断开。

[要删除结点的元素为3的结点]


删除链表的头结点的元素和删除链表的尾结点的元素
//删除链表第一个元素
	public T removeFirst(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		Node delNode = this.head;
		this.head = this.head.next;
		delNode.next =null;
		this.size--;
		return delNode.t;
	}
	//删除链表的最后一个元素
	public T removeLast(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		//只有一个元素
		if(this.getSize() == 1){
			return this.removeFirst();
		}
		Node cur = this.head;	//记录当前结点
		Node pre = this.head;	//记录要删除结点的前一个结点
		while(cur.next != null){
			pre = cur;
			cur = cur.next;
		}
		pre.next = cur.next;
		this.size--;
		return cur.t;
	}

经过上面在进行链表的结点删除的时候，会发现在删除的过程中很麻烦，还得考虑头结点（因为我们在删除结点的时候，都是先找到待删除结点del的前一个结点pre，然后直接进行跳过操作，即pre.next = pre.next.next，但是删除结点头结点的时候就无法操作），给我们添加了麻烦，为此我们可以给链表添加一个虚拟的头结点，说白了就是重新new一个结点对象，该结点对象的下一个结点指向了我们之前的头结点，让我们在删除结点的时候，无须再考虑之前的头结点了！
虚拟头结点删除链表元素的实现
//加入虚拟头结点的链表进行删除
	public void removeElt(T t){
		//构造虚拟头结点，并且下一个结点指向head
		Node dummy = new Node(t,this.head);
		//声明结点指向虚拟头结点
		Node cur = dummy;
		//从虚拟头结点的下一个结点开始遍历
		while(cur.next != null){
			if(cur.next.t.equals(t)){ 
				cur.next = cur.next.next;
				this.size--;
			}
			else cur = cur.next;
		}
		//去除虚拟头结点
		this.head = dummy.next;
	}

使用虚拟头结点进行链表的插入
刚开始那部分的结点添加是基于索引的情况实现，当我们无法知道一个结点的位于链表的哪个位置时候，只知道要插入在某个元素的前面，下面的代码基于上述情况实现。
	/**
	 * 
	 * @param t:插入在t元素的位置
	 * @param des：要插入的元素
	 */
	public void insert(T t,T des){
		//构造虚拟头结点，并且下一个结点指向head
		Node dummy = new Node(null,this.head);
		//构造要插入的结点
		Node dNode = new Node(des);
		//声明变量cur指向虚拟头结点
		Node cur = dummy;
		while(cur.next != null){
			if(cur.next.t.equals(t)){ 
				dNode.next = cur.next;
				cur.next = dNode;
				this.size++;
				break;
			}
			else cur = cur.next;
		}
		this.head = dummy.next;
	}

查找某个元素是否在链表的结点上
//链表中是否包含某个元素
	public boolean contains(T t){
		Node cur = this.head;
		while(cur != null){
			if(cur.t.equals(t)){
				return true;
			}
			else cur = cur.next;
		}
		return false;
	}

完整的代码实现：
package LinkedList;

public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;			//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
	
	//获取链表元素的个数
	public int getSize(){
		return this.size;
	}
	//判断链表是否为空
	public boolean isEmpty(){
		return this.size == 0;
	}
	//链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		// this.head = new Node(e,head);等价上述代码
		this.size++;
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
	//向链表中间插入元素
	public void add(T t,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
		if (index == 0){
			this.addFirst(t);
			return;
		}
		Node preNode = this.head;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index-1; i++){
			preNode = preNode.next;
		}
		Node node = new Node(t);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
	}
	//删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur != null && cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}
	//删除链表第一个元素
	public T removeFirst(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		Node delNode = this.head;
		this.head = this.head.next;
		delNode.next =null;
		this.size--;
		return delNode.t;
	}
	//删除链表的最后一个元素
	public T removeLast(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		//只有一个元素
		if(this.getSize() == 1){
			return this.removeFirst();
		}
		Node cur = this.head;	//记录当前结点
		Node pre = this.head;	//记录要删除结点的前一个结点
		while(cur.next != null){
			pre = cur;
			cur = cur.next;
		}
		pre.next = cur.next;
		this.size--;
		return cur.t;
	}
	//链表中是否包含某个元素
	public boolean contains(T t){
		Node cur = this.head;
		while(cur != null){
			if(cur.t.equals(t)){
				return true;
			}
			else cur = cur.next;
		}
		return false;
	}
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Node cur = this.head;
		while(cur != null){
			sb.append(cur.t+"->");
			cur = cur.next;
		}
		sb.append("NULL");
		return sb.toString();
	}
	
	public static void main(String[] args) {
		Linked<Integer> linked = new Linked();
		for(int i = 0; i < 10; i++){
			linked.addFirst(i);
			System.out.println(linked);
		}
		linked.addLast(33);
		linked.addFirst(33);
		linked.add(33, 5);
		System.out.println(linked);
		linked.remove(33);
		System.out.println(linked);
		System.out.println("删除第一个元素："+linked.removeFirst());
		System.out.println(linked);
		System.out.println("删除最后一个元素："+linked.removeLast());
		System.out.println(linked);
	}
}


总结：学链表是一种痛苦，但是痛苦并快乐着，希望能够坚持下去，把链表的全家桶都学习了，而不是这么简单的增加和删除。上述如有说的不对的地方欢迎指正！下篇文章将进行用链表实现栈和队列。