单链表的删除操作
@Override public void remove(int i) throws Exception { //删除 Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用-1表达头结点的索引 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理: 表长度小于0 或 所获结点为null if (count < 0 || p == null ){ throw new Exception("位置非法"); } //修改链指针，使待删除结点从单链表中脱离出来 p.next = p.next.next ; }
6. 单链表的建立操作
单链表是一种动态存储结构，不需要预先分配存储空间。因此，生成单链表的过程是一个结点“逐个插入”的过程。
根据插入位置的不同，可将创建单链表的方法分两种：头插法和尾插法
头插法：从表尾到表头的逆向创建；插入的位置永远是表头0
//用头插法逆位序建立单链表,其中n为单链表中的结点个数 public void create2(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //逆序输入n个结点的数据域值 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表头 insert(0,scanner.next()); } }
尾插法：从表头到表尾的创建；插入的位置永远是表尾【表的当前长度】length()
//用尾插法顺序建立单链表,其中n为单链表中的结点个数 public void create1(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //输入n个结点的数据值域 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表尾 insert(length(),scanner.next()); } }
(二) 单链表的应用举例
线性表接口
package data.linear_table; //线性表接口 public interface IList { public void clear() ; //清空 public boolean isEmpty(); //判断是否为空 public int length(); // 表的长度 public Object get(int i) throws Exception; //获取元素的值 public void insert(int i , Object x) throws Exception; //在指定位置，插入指定元素 public void remove(int i ) throws Exception; //删除指定元素 public int indexOf(Object x) ; //查找指定元素第一次出现的位置 public void display() ; //输出元素的值 }
单链表的结点类
package data.linear_table.linked_list; //单链表：结点类 public class Node { public Object data ; //存放结点值 public Node next ; // 后继结点的引用 //无参时的构造函数 public Node() { this(null,null); } //带一个参数时的构造函数 public Node(Object data) { this(data,null); } //带两个参数时的构造函数 public Node(Object data , Node next) { this.data = data ; this.next = next ; } }
单链表类
package data.linear_table.linked_list; import data.linear_table.IList; import java.util.Scanner; //单链表类 //实现线性表IList接口 public class LinkList implements IList { public Node head ; //单链表的头指针 //单链表的构造函数 public LinkList(){ //初始化头结点 head = new Node(); } //构造一个长度为n的单链表 public LinkList(int n ,boolean order) throws Exception { //初始化结点 this(); if (order){ //用尾插法顺序建立单链表 create1(n); }else { //用头插法逆位序建立单链表 create2(n); } } //用尾插法顺序建立单链表,其中n为单链表中的结点个数 public void create1(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //输入n个结点的数据值域 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表尾 insert(length(),scanner.next()); } } //用头插法逆位序建立单链表,其中n为单链表中的结点个数 public void create2(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //逆序输入n个结点的数据域值 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表头 insert(0,scanner.next()); } } //设为空链表 @Override public void clear() { head.data = null ; head.next = null ; } //判断带头结点的单链表是否为空 @Override public boolean isEmpty() { return head.next == null ; } //求带头结点的单链表长度 @Override public int length() { Node p = head.next; // 获得第一个结点 int length = 0; // 定义一个变量记录长度 while(p != null) { length ++; //计数 p = p.next; //p指向下一个结点 } return length; } @Override public Object get(int i) throws Exception { Node p = head.next; //初始化，p指向头结点 int j = 0; //计数器 //链表没有下一个 && 处理有效部分【从首结点开始向后查找，直到p指向第i个结点】 while(p != null && j < i) { //指向后继结点 p = p.next; j++; } //i 小于0 或者i 大于表长度减一时，即不合法 //解析 j > i : j = 0 时—— j > i 即 0 > i 即 i < 0 //当j遍历累加到 i-1 有效部分之后，即 j < i 即要使位置不合法，则需 j > i if(j > i || p == null) { throw new Exception("元素不存在"); } return p.data; //返回数据 } @Override //在不带头结点的单链表的第i个结点之前插入一个数据域值为x的新结点 public void insert(int i, Object x) throws Exception { //获得i前驱，结点p Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用 -1 表达头结点的索引 //请用 i= -1/0/1 去测试 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理 if (count > i || p == null ){ throw new Exception("位置非法"); } //创建一个结点，存入数据x Node s = new Node(x); //判断： 插入位置为表头时 if( i == 0 ){ s.next = head ; head = s ; }else { //插入位置为表的中间或表尾时 s.next = p.next ; p.next = s ; } } @Override public void remove(int i) throws Exception { //删除 Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用-1表达头结点的索引 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理: 表长度小于0 或 所获结点为null if (count < 0 || p == null ){ throw new Exception("位置非法"); } //修改链指针，使待删除结点从单链表中脱离出来 p.next = p.next.next ; } @Override //查询给定值的索引号，如果没有返回-1 public int indexOf(Object x) { Node p = head.next; // 初始化，p指向头结点 int j = 0; // 不匹配元素的个数，计数器 while(p != null && !p.data.equals(x)) { // 循环依次找【不匹配】元素 p = p.next; j++; } // 返回匹配索引，如果没有返回-1 if(p != null) { return j; } else { return -1; } } //输出单链表中所有的结点 @Override public void display() { //取出带头结点的单链表中的首结点 Node node = head.next; while (node != null) { //输出结点的值 System.out.println(node.data+" "); //取出下一个结点 node = node.next ; } //换行 System.out.println(); } }
例1：编程实现查找线性表(0,1,2,3,....., n-1)中第 i（[1,n]）个数据元素的直接前驱，并输出其值。并要求在单链上实现。
package data.linear_table.linked_list; import java.util.Scanner; public class Examp1 { public static void main(String[] args) throws Exception { //例1：编程实现查找线性表(0,1,2,3,....., n-1)中 // 第 i（[1,n]）个数据元素的直接前驱，并输出其值。并要求在单链上实现。 int n = 10 ; //创建一个空的单链表 LinkList L = new LinkList(); //将0，1，2，3.... 到 n-1 依次插入到表尾 for(int i = 0 ; i < n ; i++) { //调用插入方法，在第i个位置上插入数据域值为i的数 L.insert(i, i); } System.out.println("请输入i 的值："); int i = new Scanner(System.in).nextInt(); if (i > 0 && i <= n) { System.out.println("第"+i+"个元素的直接前驱是："+L.get(i-1)); }else { System.out.println("第"+i+"个元素的直接前驱不存在！"); } } }
—— 所输入i的值必须在{0，n]的范围内。第0个元素为表头，没有前驱。输出结果：
(三)顺序表与链表的比较
链表比较灵活，插入和删除操作效率较高，但空间利用率低，适用于实现动态的线性表；
顺序表实现比较简单，并且空间利用率也较高，可高效的进行随机存取，但顺序表不易扩充，插入和删除操作效率较低，适合于实现相对“稳定”的静态线性表。
-----------------------------------------------------------------------------------------------
章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！
