河池学院：《数据结构》课程电子教案（PPT教学课件）第2章 线性表 2.3 线性表的链式存储结构 2.4 顺序表和链表的比较

线性表： （a0，a1，.，ai，ai+1，.，an-1） 结点包含有元素值和前后继结点的地址信息 结点 映射 1/85

如果每个结点只设置一个指向其后继结点的指针成员，这样的链表 称为线性单向链接表，简称单链表。 头结点 开始结点 尾结点 head a0 a1 . an-1 ∧ （a）单链表 如果每个结点中设置两个指针成员，分别用以指向其前驱结点和后 继结点，这样的链表称之为线性双向链接表，简称双链表。 头结点 开始结点 尾结点 dhead a0 a1 . an-1 ∧ （b）双链表 2/85

每个结点为LinkNode泛型类对象，包括存储元素的数据成员 data（设其数据类型为E）和存储后继结点的指针成员next。 class LinkNode //单链表结点泛型类 { E data; LinkNode next; public LinkNode() //构造方法 { next=null; } public LinkNode(E d) //重载构造方法 { data=d; next=null; } } 头结点 开始结点 尾结点 head a0 a1 . an-1 ∧ 3/85

单链表泛型类LinkListClass public class LinkListClass //单链表泛型类 { LinkNode head; //存放头结点 public LinkListClass() //构造方法 { head=new LinkNode(); //创建头结点 head.next=null; //头结点next成员置为next } //基本运算算法 } head ∧ 4/85

head . ∧ 单链表对象L： L.head L.head.next 结点引用方式： 5/85

1. 插入和删除结点操作 插入结点操作：将结点s插入到单链表中p结点的后面。 . a p b . x s （b）s.next=p.next . a p b . x s （c）p.next=s . a p x b . s （d）插入后 . a p b . s x （a）插入前 6/85

删除结点操作：删除单链表中p结点的后继结点。 . a p b . （a）删除前 . a p b . （b）删除后 7/85

2. 整体建立单链表 通过一个含有n个元素的a数组来建立单链表。 建立单链表的常用方法有两种：头插法和尾插法。 8/85

从一个空表开始，依次读取数组a中的元素。 生成新结点s，将读取的数据存放到新结点的数据成员中。 将新结点s插入到当前链表的表头上。 s.next=head.next; head.next=s; head . ∧ ai s 9/85

public void CreateListF(E[] a) //头插法：由数组a整体建立单链表 { LinkNode s; for (int i=0;i(a[i]); //新建存放a[i]元素的结点s s.next=head.next; //将s结点插入到开始结点之前,头结点之后 head.next=s; } } a=('a','b','c','d')，调用CreateListF(a) head d c b a ∧ 头插法建立的单链表中数据结点的次序与a数组中的次序正好相反 10/85