如何查看网站服务器,网络公司加盟代理,开发商延期交房怎么处理,中信建设公司领导班子目录
一、链表
1.1. 链表的概念及结构
1.2. 链表的实现 专栏#xff1a;数据结构(Java版) 个人主页#xff1a;手握风云 一、链表
1.1. 链表的概念及结构 链表是⼀种物理存储结构上⾮连续存储结构#xff0c;数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的。与火车…目录
一、链表
1.1. 链表的概念及结构
1.2. 链表的实现 专栏数据结构(Java版) 个人主页手握风云 一、链表
1.1. 链表的概念及结构 链表是⼀种物理存储结构上⾮连续存储结构数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的。与火车类似火车头、车厢与每一届车厢之间由火车链连接起来。在物理上链表是不一定连续的但在逻辑上一定是连续的。 如下图所示链表的结构分为两个域一个域用来储存数据另一个域用来储存下一个节点(类似于火车的一节车厢)的地址。 与顺序表不同的是链表的地址在物理上不连续但在逻辑上是连续的。最后一个节点相当于“车尾”里面存的地址为null。这就是一个单向、不带头、非循环的链表。类似地还有双向、带头、循环的链表。但考试考最多的说就是单链表。 什么是带头的链表呢如下图所示第一个节点可以存任何数据但存取的数据是没有意义的唯一的作用就是起到一个“排头兵”的作用。不带头的链表呢相当于它的head会变的比如我们把第一个节点删掉那么第二个节点就会成为head。 那么什么又是循环链表呢如下图所示最后一个节点指向了第一个节点或第二个节点就可以构成循环链表但一般情况下我们都是指向第一个节点。 1.2. 链表的实现 接下来我们要通过代码来实现链表我们就可以定义一个MySingleList类链表当中有很多的节点基于面向对象的思想我们可以使用内部类来定义我们的节点。
public class MySingleList {static class ListNode{private int val;private ListNode next;public ListNode(int val) {this.val val;}//因为不知道下一个节点是谁所以这里的构造函数的参数里不写next。}public ListNode head;//表示当前链表的头节点public int listSize;
} 链表的基础已经写好了下面要实行链表的增、删、查、改。我们可以把这些方法写在一个接口里面。接口里面的方法默认都是public并且不需要具体的实现。然后我们在MySingleList类里面对这些方法进行重写。
public interface Ilist {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插⼊第⼀个数据节点为0 号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);public void remove(int key);//删除所有值为 key的节点public void removeAllKey(int key);//得到单链表的⻓度int size();public void clear();public void display();
}public class MySingleList implements Ilist{static class ListNode{private int val;private ListNode next;public ListNode(int val) {this.val val;}//因为不知道下一个节点是谁所以这里的构造函数的参数里不写next。public ListNode head;//表示当前链表的头节点}Overridepublic void addFirst(int data) {}Overridepublic void addLast(int data) {}Overridepublic void addIndex(int index, int data) {}Overridepublic boolean contains(int key) {return false;}Overridepublic void remove(int key) {}Overridepublic void removeAllKey(int key) {}Overridepublic int size() {return 0;}Overridepublic void clear() {}Overridepublic void display() {}
}我们也可以自己创建一个链表 public ListNode head;//表示当前链表的头节点public void CreateList(){ListNode node1 new ListNode(11);ListNode node2 new ListNode(22);ListNode node3 new ListNode(33);ListNode node4 new ListNode(44);//这些数据之间没有连续性node1.next node2;node2.next node3;node3.next node4;//node4已经是最后一个节点了不需要管最后一个nextthis.head node1;//这样可以从第一个节点开始去遍历我们的数组}public class Main {public static void main(String[] args) {MySingleList mySingleList new MySingleList();mySingleList.CreateList();System.out.println();}
} 我们在对象实例化这里打一个断点来进行调试。开始的时候头节点是空的运行到下一行时我们的val的值和next的地址都被CreateList方法串联起来了。 了解了next的引用原理之后我们就可以遍历链表来对里面的数据进行打印。我们通过上面的display方法来实现那我们如何通过head的引用从第一个节点指向第二个节点呢 //基本变量通过自增的方式来赋值
int a 10;
a a 1;//同理引用变量也可以采用上述方法
head head.next; Overridepublic void display() {while(head ! null){System.out.print(head.val );head head.next;}System.out.println();} 我们来对这个方法进行调试一下如下图所示当head不为空时进入while循环当head.next指向第二个节点时val的值变为了22next的地址也指向了第二个节点。当head指向最后一个节点时地址变为null跳出while循环。 运行结果如下 但这种写法也有致命的缺点如果说这个方法有返回值呢head遍历完我们的链表之后head引用变为了null返回的值也会成一个null如果我们再用ListCode创建一个cur变量head引用保持不动把head的引用赋值给cur再让cur去遍历链表。 比如我们通过size方法来获取链表的节点数就可以这样写 Overridepublic int size() {ListNode cur head;int count 0;while(cur ! null){cur cur.next;count;}return count;} 再比如我们去写contains方法去判断链表里是否存在关键字 Overridepublic boolean contains(int key) {ListNode cur1 head;while(cur1 ! null){if(cur1.val key){return true;}cur1 cur1.next;}return false;}System.out.println(mySingleList.contains(44));System.out.println(mySingleList.contains(45)); 可能有的老铁在写这个方法会写出cur1.next ! null因为最后一个节点的next为null当cur1走到最后节点时不满足cur1.next ! null相当与根本没有遍历完这个数组。 下面我们将要进行对链表里的数据进行增删查改。我们先来实现头插和尾插。我们如果向把一个node节点(里面存的数据是10)插入head节点前面之后node节点就变成了head节点。我们可以通过下面两行代码来实现这个过程。这里千万不能把两行代码写反因为这样就会使得node.next指向自己。
node.next head;//先让node.next的地址指向node1
head node;//再通过head引用指向node就能把node变成头节点 public void addFirst(int data) {ListNode node new ListNode(data);if(head null){head node;//相当于插入进一个空的链表}else{node.next head;head node;}}public static void main(String[] args) {Ilist mySingleList new MySingleList();mySingleList.addFirst(10);mySingleList.addFirst(20);mySingleList.addFirst(30);mySingleList.addFirst(40);mySingleList.display();} 对于尾插的实现与头插不同的是我们需要先找出链表的最后一个节点然后再让cur.next node。如果说初始的链表是空的情况下则cur nullcur.next就会出现空指针异常。我们就需要参考contains方法来寻找链表的尾部。 Overridepublic void addLast(int data) {ListNode node new ListNode(data);//表示链表为空if(head null) {head node;return;}//找到链表的尾巴ListNode cur head;while (cur.next ! null) {cur cur.next;}cur.next node;} 下面我们来实现比较复杂的在任意位置插入一个节点为了方便理解我们给每个节点都编上号。如果说我们要把新的节点插入到2号位置那么新的节点就会变成2号位置。但我们的cur是不能走两步的因为插入之后2号位置不知道前面的节点是谁这个链表是单向的所以cur不能往回走也就是要走index-1步。我们可以通过两行代码来实现这一过程。 node.next cur.next;
cur.next node; 对于cur需要走index-1步的过程我们可以重新写一个方法来实现。然后我们就可以把新节点插入到链表中了。
private ListNode findIndex(int index){ListNode cur head;int count 0;while(count ! index-1){cur cur.next;count;}return cur;}
public void addIndex(int index, int data) {ListNode node new ListNode(data);ListNode cur findIndex(index);node.next cur.next;cur.next node;listSize;} 过程确实有点复杂不懂的老铁可以去画画图去理解。到这里看似我们的过程已经结束了但我们需要考虑其他的一些问题。如果我们在0号位置插或者在5号位置插那么就相当于头插和尾插了我们就可以直接调用addFirst和addLast方法。那如果我们在-1、-2位置插呢这时就会越界访问。我们就需要写一个方法来检查访问是否合法。 if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;} private void checkIndexOfAdd(int index){if(index0 || indexsize()){throw new RuntimeException(插入的位置不合法,indexindex);}}
public class IndexOutOf extends RuntimeException{public IndexOutOf() {}public IndexOutOf(String message) {super(message);}
}try {mySingleList.addIndex(6,99);}catch (IndexOutOf e) {e.printStackTrace();} 接下来我们看删除元素。删除并不是简单的跳过这个节点还要把要删除的节点前一个和后一个连接起来。那我们先找到要删除元素的前一个元素我们又该如何找到要删除的节点呢
cur.next del.next; rivate ListNode findNode(int key) {ListNode cur head;while (cur.next ! null) {if(cur.next.val key) {return cur;}cur cur.next;}return null;} 通过上面这个方法我们就可以找到我们要删除的节点。注意我们不能写成cur ! null因为cur.next就会空指针异常。如果我们没有找到就返回null。但是我们需要考虑一下我们要删除第一个数据cur已经在第一个节点那么cur.next就不会对第一个节点进行判断从而就不会删除。 Overridepublic void remove(int key) {if(head null) {return;}if(head.val key) {head head.next;listSize--;return;}ListNode cur findNode(key);if(cur null) {System.out.println(没有你要删除的数据);return;}ListNode del cur.next;cur.next del.next;listSize--;}
