线性表的链式存储-单链表

单链表头指针head和终端结点单链表的实现代码项目目录结构基本的结构体接口中的抽象方法实现类 线性表的总结对与线性表中的基本操作的时间复杂度

单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据域) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

头指针head和终端结点

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。

终端结点无后继，故终端结点的指针域为空，即NULL。

单链表的实现代码

项目目录结构

结构体 ListNode.java接口类 MyList.java实现类 SingleLinkedList.java

基本的结构体

ListNode.java:

package day01线性表;/*单链表的实现*/public class ListNode {private Object data;//数据域private Object next;//指针域public ListNode(Object data) {this.data = data;}// getter 和 setter 方法，对应着c语言中的结构体指针指向// 也可以修改 data 和 next 两个成员变量的访问控制权限 ，直接通过 对象.成员变量来做public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Object getNext() {return next;}public void setNext(Object next) {this.next = next;}}

接口中的抽象方法

MyList.java:

package day01线性表;public interface MyList {/*** 添加元素* @param element*/void add(Object element);/*** 在指定位置插入元素* @param target* @param element*/void add(int target,Object element);/*** 根据元素的值来删除* @param element*/void delete(Object element);/*** 根据索引来删除元素* @param index*/void delete(int index);/*** 根据指定的target索引位置来更新元素* @param traget* @param element*/void update(int traget,Object element);/*** 返回某一元素第一次在线性表中出现的位置* @param element* @return*/int indexOf(Object element);/*** 返回在指定target位置的元素* @param target* @return*/Object elementAt(int target);/*** 取指定索引位置元素的前驱元素* @param index* @return*/Object elementPrior(int index);/*** 取指定索引位置元素的后继元素* @param index* @return*/Object elementNext(int index);/*** 是否包含某一元素* @param element* @return*/boolean contains(Object element);}

实现类

SingleLinkedList.java:

package day01线性表;import java.util.LinkedList;public class SingleLinkedList implements MyList{private ListNode head;//头节点private ListNode last;//尾节点private int size;//记录节点个数@Overridepublic void add(Object element) {if(head==null){//一开始，头尾结点指向同一处head = new ListNode(element);last = head;}else{//尾插法last.setNext(new ListNode(element));//将 last 移动到自己的后继元素上last = (ListNode) last.getNext();}size++;}@Overridepublic void add(int target, Object element) {//这里这个指定位置插入，对于单链表意义不大，所以就忽略不写了}@Overridepublic void delete(Object element) {//同样还是先记录头结点ListNode p = head;ListNode pre = null;//前驱节点一开始为空，方便后来的删除// 因为单链表中的删除，就是将要删除的节点的前驱，直接指向要删除节点的后继节点while (p!=null){if(p.getData().equals(element)){//如果删除的是头节点的值，那么就直接修改head指向即可if(p==head){head = (ListNode) head.getNext();size--;return;}else {// 删除节点的前驱指向删除节点的后继pre.setNext(p.getNext());size--;return;}}//没找到就一直往后面移动 pre 和 ppre = p;p = (ListNode) p.getNext();}//如果就是整个链表中都没找到则打印输出System.out.println("当前链表中中不存在值为"+element.toString()+"的元素，无法删除!");}@Overridepublic void delete(int index) {//index越界判断if(index<0||index>=size){System.out.println("要访问的索引已经越界!无法进行删除");return;}int i = 0;//一开始头节点的索引为0ListNode p = head;ListNode pre = null;//头节点的前驱节点为空while (p!=null){if(i==index){//如果删除的是头节点的值，那么就直接修改head指向即可if(p==head){head = (ListNode) head.getNext();size--;return;}else {// 删除节点的前驱指向删除节点的后继pre.setNext(p.getNext());size--;return;}}//没找到就一直往后面移动 pre 和 ppre = p;p = (ListNode) p.getNext();i++;}}@Overridepublic void update(int traget, Object element) {//index越界判断if(traget<0||traget>=size){System.out.println("要访问的索引已经越界!无法进行修改");return;}int i = 0;//一开始头节点的索引为0ListNode p = head;while (p!=null){if(i==traget){p.setData(element);return;}//没找到就一直往后面移动 pp = (ListNode) p.getNext();i++;}}@Overridepublic int indexOf(Object element) {int i = 0;ListNode p = head;while(p!=null){if(p.getData().equals(element)){return i;}p = (ListNode) p.getNext();i++;}return -1;//整个链表中并没有对应的元素，则返回-1}@Overridepublic Object elementAt(int target) {if(target<0||target>=size){System.out.println("索引越界,已经超过链表的元素个数");return null;}int i = 0;ListNode p = head;while (p!=null) {if (i == target) {return p.getData();}p = (ListNode) p.getNext();i++;}return null;}@Overridepublic Object elementPrior(int index) {//索引越界if(index-1<0||index>size){return null;}int i =0;ListNode p = head;while (p!=null){if (i==index-1){return p.getData();}p = (ListNode) p.getNext();i++;}return null;}@Overridepublic Object elementNext(int index) {//索引越界if(index<0||index+1>size){return null;}int i =0;ListNode p = head;while (p!=null){if (i==index+1){return p.getData();}p = (ListNode) p.getNext();i++;}return null;}@Overridepublic boolean contains(Object element) {ListNode p = head;while (p!=null){if(p.getData().equals(element)){return true;}p = (ListNode) p.getNext();}return false;}@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");ListNode p = head;while (p!=null){stringBuilder.append(p.getData());if(p.getNext()!=null){stringBuilder.append(",");}p = (ListNode) p.getNext();}stringBuilder.append("]");return stringBuilder.toString();}public static void main(String[] args) {SingleLinkedList list = new SingleLinkedList();list.add("a");list.add("b");list.add("c");list.add("d");list.add("e");System.out.println(list);list.delete("c");System.out.println(list);list.delete("a");System.out.println(list);list.delete("g");list.update(0,"x");System.out.println(list);list.delete(0);System.out.println(list);list.delete(10);list.update(3,"a");list.add("a");System.out.println(list);list.contains("a");System.out.println(list.elementAt(2));System.out.println(list.indexOf(1));System.out.println(list.indexOf("d"));System.out.println(list.indexOf("e"));list.add("b");list.add("g");System.out.println(list);System.out.println(list.elementPrior(1));System.out.println(list.elementNext(3));System.out.println(list.elementNext(5));}}

这里mian方法最后的输出为：

线性表的总结

结合上一篇的顺序存储的总结java数据结构，线性表顺序存储（数组）的实现

对于顺序存储，按顺序放在一起，相邻元素通过内存地址相邻产生联系，”随机存取“。而链式存储，元素随机放置在内存中任意位置，每个元素除了存放数据，也保存了其相邻元素的内存地址，来实现线性关系，“随机存取”。单链表的存储空间会比相同元素个数的线性表多，原因是单链表中包括了数据域data和指针域next,所以其存储密度是小于1的。

对与线性表中的基本操作的时间复杂度

1.查找元素，按值查找。

给定长度为 n 的线性表，查找值为 v 的元素。(最坏)从头到尾遍历 => 时间复杂度O(n)

2.新增或者删除元素

对于顺序表来说，新增或者删除元素，需要对应的右移或者左移，最坏的情况是挪动所有元素的位置，时间复杂度为O(n)，空间复杂度为O(1).对于单链表来说，新增或者删除元素，只需要修改前驱元素的next即可。因线性链表在插⼊或删除时，不需要移动元素，只要修改指针，⼀般情况下时间复杂度为O(1)。但是，如果要在单链表中进⾏前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。进⾏插⼊和删除的操作是常数即便，但是寻找前驱才要O(n)。空间复杂度为O(1).

3.更新元素

顺序表更新元素可以直接访问数组下标去进行修改，时间复杂度为O(1).单链表则需从头节点开始遍历，最坏的情况是遍历整个链表，时间复杂度为O(n).

到此结束啦！java数据结构代码实现持续更新中!萌新学习笔记！