2.3.3 类定义
- 数据域 data：用于存放数据元素的值。
- 指针域 next：用于存放后继结点的地址。
publicclassNode{ publicObjectdata; //数据域publicNodenext; //指针域}
2.3.4 算法：单链表的长度【重点】
publicintlength() { Nodep=head.next; // 获得第一个结点intlength=0; // 定义一个变量记录长度while(p!=null) { length++; //计数p=p.next; //p指向下一个结点 } returnlength; }
2.3.5 算法：按索引号(位序号)查找【重点】
- 思路：
- 处理了所有的结点都没有数据，判断依据 null
- 处理到一部分就找到了，判断依据
publicObjectget(inti) { Nodep=head.next; //获得头结点intj=0; //已经处理的结点数while(p!=null&&j<i) { //链表没有下一个 && 处理有效部分p=p.next; j++; } if(i<0||p==null) { thrownewException("元素不存在"); } returnp.data; //返回数据}
2.3.6 算法：按值查找索引号【重点】
//查询给定值的索引号，如果没有返回-1publicintindexOf(Objectx) { Nodep=head.next; // 获得头结点intj=0; // 不匹配元素的个数while(p!=null&&!p.data.equals(x)) { // 循环依次找【不匹配】元素p=p.next; j++; } // 返回匹配索引，如果没有返回-1if(p!=null) { returnj; } else { return-1; } }
2.3.7 算法：插入
- 需求：向索引i前面插入一个新结点s
- 思路：获得i的前驱，结点P
publicvoidinsert(inti , Objectx) { Nodep= ...; // 获得i前驱，结点pNodes=newNode(x); //创建新结点ss.next=p.next; //必须先执行p.next=s; //然后再执行}
2.3.8 算法：删除
- 需求：删除i结点
publicvoidremove(inti) { // 获得i的前驱结点pp.next=p.next.next; }
2.3.9 算法：获得前驱
// i最小值0，表示获得头结点head// 算法内部，使用-1表示头结点head，结点移动从头结点head开始。publicvoidprevious(inti) { Nodep=head; //从头结点head开始移动intj=-1; //使用-1表示头结点的索引while(p!=null&&j<i-1 ) { // i-1前驱的下标p=p.next; j++; } if(p==null||i<0) { // i-1 < jthrownewRuntimeException("i不合法"); } //p就是需要获得前驱}
2.4 循环链表
2.4.1 定义
- 循环链表也称为环形链表，其结构与单链表相似，只是将单链表的首尾相连。
// p结点是尾结点
p.next = head;
2.4.2 算法：循环链表合并
- 分析
核心算法/* 变量a尾: tailaa头：taila.nextb尾：tailbb头：tailb.next*/// 先将b尾指向a的头，需要定义p记录b尾原来的值// 再将a的尾指向b的头Nodep=tailb.next; //记录b尾的指向，也就是b头tailb.next=taila.next; //b尾指向a头taila.next=p.next; //a尾执行b头
2.5 双向链表
2.5.1 定义
- 一个结点由两个指针域，一个指针域指向前驱结点，另一个指针域指向后继结点，这种链表称为双向链表
- 数据域 data
- 前驱结点指针域：prior
- 后继结点指针域：next
2.5.2 算法：插入
- 需求：向结点p前面插入新结点s
/* 变量结点a：p.prior*/p.prior.next=s; //结点a指向结点ss.prior=p.prior; // 结点s指向结点ap.prior=s; //结点p指向结点ss.next=p; //结点s执行结点p//注意：必须先处理结点a，否则无法获得结点a
2.5.3 算法：删除
- 需求：删除p结点
// a.next = bp.prior.next=p.next; // b.prior = ap.next.prior=p.prior
