线性表之单链表 - part03
线性表之单链表 - part03
链式表的概念与表示
链表的概念
1.定义：用一组物理位置任意的存储单元来存放数据元素。逻辑次序与物理次序不一定相同。在存储元素本身的同时，还存储下一个元素的地址。
头指针记录第一个元素的地址，之后每个结点=数据域+指针域。
链表是n个结点由指针链组成的表。
单链表由头指针唯一确定，因此单链表可以用头指针名字来命名。
2.分类：单链表、双链表、循环链表。
3.头结点：
链表中可以有头结点，也可以无头结点。头结点的数据域可以为空，不计入链表长度。
如何表示空表：
（无头结点）头指针为空、（有头结点）头结点的指针域为空。
设置头结点的好处：
便于首元结点的处理，首元结点与其他结点相同了。
便于空表与非空表的统一处理，头指针都是指向头结点的非空指针。
4.特点：
访问只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点。
单链表的定义与表示
构造结点类型，结点包含数据域（数据的类型）+指针域（结点类型）
用定义头指针来定义链表L：LinkList L;
定义结点指针p: Lnode p
指针的类型是它所指向的数据的数据类型，如next类型就是结点类型。对某一类型定义指针，表示这是指向此类型数据的指针类型，如LinkList就是指向结点类型的指针类型。
单链表的基本操作的实现
1.单链表的初始化
重要说明：
L->next 即 (*L).next //L表示指针，L表示指向的结点内容。
L=new LNode; 表示L指针指向新建结点，java中无指针，但也是此含义。
&L表示引用，如果所做的操作会影响L的结果就加引用，如果只是查询之类不修改表，则不需要引用。有引用则函数中不需要设置返回值，直接表示返回该引用值。
2.单链表的销毁
有链表L，建立指针p指向头结点即p=L，L向右移，删除p。p=L，再把L指针往右移，删除p。当L移到空位置时，p指向的头结点删除，完成销毁。
3.单链表的清空
如果从头结点开始操作，则p指针定义为：p=L;
如果从首元结点开始操作，则p指针定义为：p=L->next;
新建p指针指向首元结点。新建q指针为p向右移（q=p->next;），删除p，令p=q。q再往右移，再删除p，再令p=q。直到p为空，则令头结点指针域为空，清空结束。
3.求单链表的表长
4.单链表的取值（取第i个元素的内容）
从首元结点找起，若是找第一个结点就直接跳出循环了。循环终止条件是p&&j<i（p为空表示i大于链表本身长度情况，没找到情况；j<i为零表示j>i位置i不在我们搜索位置之后，或者j=i已找到位置）。
5.单链表的按值查找
从首元结点开始找，循环终止条件是p&&p->data!=e（p为空表示没找到；后者表示已找到）。
6.单链表的插入操作
从头结点开始考虑，因为要找的是i-1位置的结点。循环终止条件就是找到i-1的位置：p&&j<i-1。
根据需要插入的元素建立新指针。先处理新指针向后的指向，再处理前边指向新指针的指向。
注意返回error的条件就是循环终止条件的“非”。
7.单链表的删除操作
p在循环中对应指向的是第j个结点。
查找结点时可以查找最后一个结点；插入新结点时，查找的i-1结点也可以是最后一个。
但是删除结点时，i-1结点不能是最后一个，因为后面已经没有结点能删除了。所以循环终止条件跟前边不同。
找i-1位置的结点，从头结点开始，循环终止条件为p->next&&j<i-1。
找i-1位置，给被删节点结点赋新指针等于左边的指向，i-1结点的指向等于q向右边的指向。
单链表基本操作的算法分析
查找：O（n）
插入和删除：只考虑这个动作 O（1）
在单链表中插入或删除，考虑从头查找前驱结点：O（n）
单链表的建立
头插法
把元素插入在链表头部。
建立头结点，建立新结点（相当于建立p指针，指针p就代表新结点）存入新数据，先确定新结点往右的指向（头结点指向），再确定新结点往左的链接。
尾插法
把元素插入在链表尾部。在插入时新建一个尾指针。
建立头结点/初始链表，新建尾指针，新建结点存入数据，把往右指向的指针域置空，确定往左与r尾指针链接，再让r指向尾结点与p相同。