【数据结构】虽然很难很抽象，但是你还是得努力弄懂的数据结构

2023-06-06 07:21| 来源: 网络整理| 查看: 265

链表解决了顺序表插入或删除元素麻烦的问题，链表的存储结构是用一组任意的存储单元来存放线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

对每个数据元素ai，除了存储其本身的信息之外，还需存储一个指示其直接后继存放位置的指针。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。如下图所示：在这里插入图片描述

结点类的泛型定义如下，数据域为data，指针域为next。构造器有两个，二者的区别是参数个数不同。有一个参数的构造器，用参数n来初始化next指针域，数据域不存储有效的用户数据。有两个参数的构造器，根据形参obj和n分别初始化数据域data和指针域next。

public class Node { //数据 T data; //指针 Node next; public Node(Node next) { this.next = next; } public Node(T data, Node next) { this.data = data; this.next = next; } }

线性表链式存储结构如下图所示：在这里插入图片描述其泛型类的定义如下，

public class SingLinkList { // 头指针 private Node head; //单链表的长度 private int length; /** * 单链表初始化 */ public SingLinkList() { length=0; head = new Node(null); } ... }

在SingLinkList类中有两个成员变量。一个是指向头结点的指针head，习惯称head为头指针；另一个是length，用来存放单链表的长度。类中的基本方法和顺序表中的基本方法实现的功能是一样的，但具体实现有所区别。

在无参构造方法中，设置length值为0即初始化线性表为空。通过new创建的结点对象调用了Node(Noden)构造方法，它的作用是将next指针域初始化为null，数据域data未进行初始化，所以head所引用的这个结点称之为头结点。通过头结点的next指针域可以找到链表中的第一个结点。

单链表的插入是指在单链表的第pos-1个结点和第pos个结点之间插入一个新的结点，要实现结点的插入，需修改插入位置之前的结点和当前插入结点的指针指向，过程如下图：在这里插入图片描述

具体实现代码如下：

/** * 单链表的插入,需要把插入位置的上一个节点和下一个节点先找出来,然后插入时间复杂度为O(n) * @param obj 需要插入的元素 * @param pos 需要插入的位置 * @return */ public boolean add(T obj,int pos){ if (pos length+1) { throw new LinkException("pos值不合法"); } int num =1; // 当前节点, 需要从头开始查找 Node p = head; // 下一个结点 Node q = head.next; // 从头结点开始一个个找到需要删除的结点 while (num if (isEmpty()){ throw new LinkException("链表为空"); }else { if (pos length) { throw new LinkException("pos值不合法"); } int num =1; // 当前节点, 需要从头开始查找 Node p = head; // 下一个结点 Node q = head.next; // 从头结点开始一个个找到需要删除的结点 while (num if (isEmpty()){ throw new LinkException("链表为空"); } int num=1; // p引用的是头结点之后的节点 Node p=head.next; //如果单链表不为空 while (p!=null){ //如当前节点的data不等需要查找的值,就继续查找下一个节点 if (!p.data.equals(obj)){ p = p.next; num++; }else { break; } } if (p == null){ return -1; } return num; }

单链表的完整实现如下：

public class SingLinkList { // 头指针 private Node head; //单链表的长度 private int length; /** * 单链表初始化 */ public SingLinkList() { length=0; head = new Node(null); } /** * 获取单链表头结点的地址 * @return */ public Node getHead(){ return head; } /** * 单链表的插入,需要把插入位置的上一个节点和下一个节点先找出来,然后插入时间复杂度为O(n) * @param obj 需要插入的元素 * @param pos 需要插入的位置 * @return */ public boolean add(T obj,int pos){ if (pos length+1) { throw new LinkException("pos值不合法"); } int num =1; // 当前节点, 需要从头开始查找 Node p = head; // 下一个结点 Node q = head.next; // 从头结点开始一个个找到需要删除的结点 while (num if (isEmpty()){ throw new LinkException("链表为空"); }else { if (pos length) { throw new LinkException("pos值不合法"); } int num =1; // 当前节点, 需要从头开始查找 Node p = head; // 下一个结点 Node q = head.next; // 从头结点开始一个个找到需要删除的结点 while (num if (isEmpty()){ throw new LinkException("链表为空"); } int num=1; // p引用的是头结点之后的节点 Node p=head.next; //如果单链表不为空 while (p!=null){ //如当前节点的data不等需要查找的值,就继续查找下一个节点 if (!p.data.equals(obj)){ p = p.next; num++; }else { break; } } if (p == null){ return -1; } return num; } /** * 获取单链表第pos个结点的值, 从头节点开始往下查找, 时间复杂度为O(n) * @param pos 需要查找的结点位置 * @return 需要查找的结点位置对应的值data */ public T value(int pos){ if (isEmpty()){ throw new LinkException("链表为空"); }else{ if (poslength){ throw new LinkException("pos值不合法"); } //当前节点的位置 int num =1; Node q =head.next; while (num if (isEmpty()){ throw new LinkException("链表为空"); }else { if (pos length) { throw new LinkException("pos值不合法"); } //当前节点的位置 int num =1; Node q =head.next; while (num return length; } /** * 清空单链表 */ public void clear(){ length=0; head.next= null; } /** * 打印节点的元素 */ public void show(){ System.out.println(""); System.out.print("打印节点元素:"); //获取头节点的下一个节点 Node p= head.next; while (p!=null){ System.out.print(p.data+"-->"); //获取下一个节点 p =p.next; } } /** * 判断单链表是否为空 * @return */ public boolean isEmpty(){ return length==0; } public static void main(String[] args) { SingLinkList singLinkList = new SingLinkList(); int l,i; int[] a ={10,12,3,8,6,4,9}; l=a.length; for (i=0;i //数据 T data; //前指针 Node prior; //后指针 Node next; public Node(T data) { this.data = data; prior=null; // next=null; } public Node(T data, Node prior, Node next) { this.data = data; this.prior = prior; this.next = next; } }

双向链表图示如下：在这里插入图片描述

和单链表类似，双向链表也可以有循环表，循环双向链表图示如下：在这里插入图片描述

由于循环单链表、双向链表、循环双向链表不是本文的重点，具体不在赘述。有兴趣的的小伙伴可自行阅读相关数据结构与算法的书籍。

【本文地址】

公司简介

联系我们