[数据结构与算法]数据结构笔记--对单链表的理解

对物理结构的深化理解

单链表虽然在逻辑结构上是链状的存储着数据的结构，但是在物理结构是不过是一个个不一定相邻的节点。在对单链表进行操作的时候，有时对物理结构的考虑更重于逻辑结构。单链表的物理结构就好像一片乌黑的空间，里面不规则的散布着一些房子，每一个房子存放着些东西和去往下一个房子的地址，对于这个房子可以去往的下一个房子就叫后继节点，存放着这个房子地址的就叫做前驱节点。

单链表的一些操作

查找

一个节点在单链表的特征有两个，它存放的数据和它在整个单链表的位置。因此根据根据位置或节点存放的数据就可以确定节点的存在，即按位查找和按值查找。
上述按位查找，可以从头结点开始一个一个往后数，一直数到我们要找的第几个节点。
按值查找，也是可以从头节点开始一个一个和我们要找的值做比较，找到那个存放的值和我们要找的值相同的节点。
代码如下：

LNode*GetElem(LinkList L,int i){
	if(i<0)
		return NULL;
	LNode *p;
	int j;
	p=L;
	while(p!==NULL&&j<i){
		p=p->next;
		j++;
	}
	return p;

}

LNode*GetElem(LinkList L,int i){
	if(i<0)
		return NULL;
	LNode *p;
	int j;
	p=L;
	while(p!==NULL&&j<i){
		p=p->next;
		j++;
	}
	return p;

}

插入

想要在一个单链表里面插入或者说增加一个节点，我们需要给这个节点找到它要待的位置，实际上就是找到他的相邻节点，并且让前驱节点存放它的位置，让它存放后继节点的位置。
假设这个节点s要待的位置是i,那么原来第i-1就是他的前驱节点，第i是他的后继节点。我们可以从头节点开始，一直查找到第i-1个节点，然后让第i-1个存入s的地址，然后s存入原来第i个节点的地址。这样s就被插入到单链表当中，这种插入方式叫做后插操作
那么现在存在一个节点p，需要将s插入到p的前面去。实际上对于节点来说它存在的意义只要存放的内容和下个节点的地址。我们可以先将s插入到p的后面，然后替换s和p存放的内容，这样实际上s也是算到了p的前面