线性表的Java实现--链式存储(单向链表)
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。
链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储,链表在插入、删除数据元素时比顺序存储要快,但是在查找一个节点时则要比顺序存储要慢。
使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点,链表结构可以充分利用内存空间,实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点,同时增加了节点的指针域,空间开销较大。
下图就是最简单最一般的单向链表:
新增节点:
将值为element的新节点插入到第index的位置上。
首先要先找到索引为index-1的节点,然后生成一个数据为element的新节点newNode,并令index-1处节点的next指向新节点,新节点的next指向原来index处的节点。
删除节点:
删除第index个节点,第index节点是由index-1出的节点引用的,因此删除index的节点要先获取index-1处的节点,然后让index-1出节点的next引用到原index+1处的节点,并释放index处节点即可。
单向链表的Java实现
下面的程序分别实现了线性表的初始化、获取线性表长度、获取指定索引处元素、根据值查找、插入、删除、清空等操作。
package com.liuhao.algorithm; public class LinkList<T> { // 定义一个内部类Node,代表链表的节点 private class Node { private T data;// 保存数据 private Node next;// 指向下个节点的引用 // 无参构造器 public Node() { } // 初始化全部属性的构造器 public Node(T data, Node next) { this.data = data; this.next = next; } } private Node header;// 保存头结点 private Node tail;// 保存尾节点 private int size;// 保存已含有的节点数 // 创建空链表 public LinkList() { header = null; tail = null; } // 已指定数据元素创建链表,只有一个元素 public LinkList(T element) { header = new Node(element, null); // 只有一个节点,header,tail都指向该节点 tail = header; size++; } // 返回链表的长度 public int length() { return size; } // 获取指定索引处的元素 public T get(int index) { return this.getNodeByIndex(index).data; } //获取指定位置的节点 private Node getNodeByIndex(int index){ if(index < 0 || index > size-1){ throw new IndexOutOfBoundsException("索引超出线性表范围"); } Node current = header;//从header开始遍历 for(int i=0; i<size && current!=null; i++,current=current.next){ if(i == index){ return current; } } return null; } //按值查找所在位置 public int locate(T element){ Node current = header; for(int i=0; i<size && current!=null; i++, current=current.next){ if(current.data.equals(element)){ return i; } } return -1; } //指定位置插入元素 public void insert(T element, int index){ if(index < 0 || index > size){ throw new IndexOutOfBoundsException("索引超出线性表范围"); } //如果是空链表 if(header == null){ add(element); } else{ //当index为0时,即在链表头处插入 if(0 == index){ addAtHead(element); } else{ Node prev = getNodeByIndex(index - 1);//获取前一个节点 //让prev的next指向新节点,新节点的next指向原来prev的下一个节点 prev.next = new Node(element, prev.next); size++; } } } //在尾部插入元素 public void add(T element) { //如果链表是空的 if(header == null){ header = new Node(element, null); //只有一个节点,headwe,tail都该指向该节点 tail = header; } else{ Node newNode = new Node(element, null);//创建新节点 tail.next = newNode;//尾节点的next指向新节点 tail = newNode;//将新节点作为尾节点 } size++; } //头部插入 public void addAtHead(T element){ //创建新节点,让新节点的next指向header //并以新节点作为新的header Node newNode = new Node(element, null); newNode.next = header; header = newNode; //若插入前是空表 if(tail == null){ tail = header; } size++; } //删除指定索引处的元素 public T delete(int index){ if(index < 0 || index > size-1){ throw new IndexOutOfBoundsException("索引超出线性表范围"); } Node del = null; //若要删除的是头节点 if(index == 0){ del = header; header = header.next; } else{ Node prev = getNodeByIndex(index - 1);//获取待删除节点的前一个节点 del = prev.next;//获取待删除节点 prev.next = del.next; del.next = null;//将被删除节点的next引用置为空 } size--; return del.data; } //删除最后一个元素 public T remove(){ return delete(size - 1); } //判断线性表是否为空 public boolean isEmpty(){ return size == 0; } //清空线性表 public void clear(){ //将header,tail置为null header = null; tail = null; size = 0; } public String toString(){ if(isEmpty()){ return "[]"; } else{ StringBuilder sb = new StringBuilder("["); for(Node current = header; current != null; current = current.next){ sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len-2, len).append("]").toString(); } } }
测试代码
package com.liuhao.test; import org.junit.Test; import com.liuhao.algorithm.LinkList; public class LinkListTest { @Test public void test() { // 测试构造函数 LinkList<String> list = new LinkList("好"); System.out.println(list); // 测试添加元素 list.add("ni"); list.add("没"); System.out.println(list); // 在头部添加 list.addAtHead("五月"); System.out.println(list); // 在指定位置添加 list.insert("摩卡", 2); System.out.println(list); // 获取指定位置处的元素 System.out.println("第2个元素是(从0开始计数):" + list.get(2)); // 返回元素索引 System.out.println("摩卡在的位置是:" + list.locate("摩卡")); System.out.println("moka所在的位置:" + list.locate("moka")); // 获取长度 System.out.println("当前线性表的长度:" + list.length()); // 判断是否为空 System.out.println(list.isEmpty()); // 删除最后一个元素 list.remove(); System.out.println("调用remove()后:" + list); // 获取长度 System.out.println("当前线性表的长度:" + list.length()); // 删除指定位置处元素 list.delete(3); System.out.println("删除第4个元素后:" + list); // 获取长度 System.out.println("当前线性表的长度:" + list.length()); // 清空 list.clear(); System.out.println(list); // 判断是否为空 System.out.println(list.isEmpty()); } }
代码获取地址:https://github.com/liuhao123/JavaMore.git
相关推荐
实验内容及要求: 从字符文件输入两个多项式的非零系数及对应的指数,建立多项式的链式存储结构,计算这两个多项式的乘积,输出乘积多项式的全部...实验目的:掌握单向链表的基本操作以及基于链表的多项式加法与乘法。
带头结点的单向链式线性表,实现遍历,插入,删除,按序插入,清空
包含单向链表的插入,删除,遍历 含有前插法,尾插法等链表操作 适用于数据结构初学者使用 线性表的单链表存储结构,整个链表的存取必须从头指针开始进行,头指针指示链表中第一个结点 (第一个数据元素的存储映像,...
试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1,a2...,an)逆置为(an,an-1,...,a1)。 选题9:(难)单链表拆分。 将带头结点的单链表LA中分拆成LB和LC两条单链表,LA中的data域...
(1)使用指针和引用两种方式,完成两个学生的交换。 (2)定义一个结构体类型student,写一个...(3)完成线性表的基本操作:插入、删除、查找,遍历、以及线性表合并等运算在顺序存储结构和链式存储结构上的运算。
本科教学初学者适用 一些简单的算法 实验一 线性表的顺序存储结构 实验二 链式存储结构(一)----单向链表的有关操作等
3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算:插入、删除和搜索。( ) 6、数据结构概念包括...
单链表:它是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点。 今天我们来实现一些单链表的简单接口 先看看单链表的结构: (为了通用性,我们将类型重命名为DataType...
链表实际上是线性表的链式存储结构,与数组不同的是,链式存储并不要求数据项都顺序存放,可以散落在内存的各个角落。且链表的长度不是固定的,链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作 ...
循环链表和单向链表基本一致,差别仅在于算法中循环的条件不是结点的指针是否为空,而是他们的指针是否等于头指针, 循环链表最后一个结点的 link 指针不为 0 (NULL),而是指向了表的前端。 为简化操作,在循环链表...
另外一个链表存储已结束进程,要求使用单向链表,按照结束时间离当前时间的关系排序,最近的最前,最远的最后; (2)每秒在窗口内更新一次当前系统进程情况,输出內容包括:进程名,持续时间,内存使用情况; (3...
另外一个链表存储已结束进程,要求使用单向链表,按照结束时间离当前时间的关系排序,最近的最前,最远的最后; (2)每秒在窗口内更新一次当前系统进程情况,输出內容包括:进程名,持续时间,内存使用情况; (3...
12. 数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。( ) 【华南理工大学 2002 一、5(1分)】 13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( ) ...
6.1 单向链表 6.1.1 描述 6.1.2 结构chainNode 6.1.3 类chain 6.1.4 抽象数据类型linearList的扩充 6.1.5 类extendedChain 6.1.6 性能测量 6.2 循环链表和头节点 6.3 双向链表 6.4 链表用到的词汇表 6.5 应用 6.5.1 ...
leetcode 2 sum c 1. ACM Basic [1.8.2. list子串 1.1. Reference ...数组存储线性表 ...从数组中创建单向链表(lc83) def create_linklist(list_elems): node = ListNode(0) node_ret = node for i in list_ele
单向链表 C. 双向链表 D. 随机存储 二、判断题(每题2分,共30分) 1. CAD在早期是英文Computer Aided Design(计算机辅助设计)的缩写。× 2. 数值、字符是数据,图形、图像不是数据。× 3. 关键字是指可以用来...