双线主机可以做彩票网站吗,王者荣誉网站怎么做,作业3 主题资源网站建设,东莞理工学院目录
一、链表的简单介绍 二、链表的接口
三、链表的方法实现
#xff08;1#xff09;display方法
#xff08;2#xff09;size得到单链表的长度方法
#xff08;3#xff09;addFirst头插方法
#xff08;4#xff09;addLast尾插方法
#xff08;5#xf…目录
一、链表的简单介绍 二、链表的接口
三、链表的方法实现
1display方法
2size得到单链表的长度方法
3addFirst头插方法
4addLast尾插方法
5addIndex指定位置插入方法
6contains方法
7remove删除第一个key值节点的方法
8removeAllKey删除所有值为key的方法
9clear方法
四、最终代码 一、链表的简单介绍
概念链表是一种物理存储结构不连续逻辑上是连续的链表类似现实中的火车一节车厢连着一节车厢而链表是通过链表之间的引用进行连接构成一节一节的数据结构。如图 二、链表的接口
代码如下
public interface Ilist {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}三、链表的方法实现
创建一个类实现接口重写方法链表中的方法都在里面实现。类里面有链表类也是内部类有val值next域还有记录第一个节点的头结点代码如下
public class MyLinkedList implements Ilist{public ListNode head;static class ListNode{int val;ListNode next;public ListNode(int val) {this.val val;}}
}
我们先创建一个方法方法里面会创建几个节点代码如下
public void createList() {ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;}
调用这个方法就会创建出含有5个节点的链表在test类里面创建main方法调用此方法后的结果结果如图 1display方法
此方法可以显示链表中所有元素也就是遍历一遍链表打印val值代码如下
public void display() {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}
调用该方法执行结果如下
2size得到单链表的长度方法
要得到链表的长度就要遍历一遍链表定义一个变量进行统计个数代码如下
public int size() {int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}
执行结果 3addFirst头插方法
头插就要把要插入的节点当做头结点要插入的元素next域指向当前头结点再把头结点定成插入的元素。
代码
public void addFirst(int data) {ListNode node new ListNode(data);if(this.head null) {this.head node;} else {node.next this.head;this.head node;}}
调用此方法多条语句后的执行结果如下
4addLast尾插方法
尾插就是要在链表的尾节点后插入节点代码如下
public void addLast(int data) {ListNode node new ListNode(data);if(this.head null) {this.head node;} else {ListNode cur this.head;while (cur.next ! null) {cur cur.next;}cur.next node;}}
执行结果如下 5addIndex指定位置插入方法
我们这里规定第一个节点的位置是0第二个节点位置为1依次往后推我们要指定某一位置插入节点先要检查插入位置是否合法不合法抛出异常合法在指定位置插入节点如果指定位置是0就是头插指定位置是节点个数的size就是尾插中间位置我们要找到指定位置的前一个节点插入节点的next域指向前一个节点的next节点前一个节点的next域指向插入节点代码如下 public void addIndex(int index, int data) {try {if(index 0 || index size()) {throw new IndexException(下标异常,下标: index);} else {if(index 0) {//头插addFirst(data);return;}if (index size()) {//尾插addLast(data);return;}ListNode node new ListNode(data);ListNode cur searchPrev(index);node.next cur.next;cur.next node;}} catch (IndexException e) {e.printStackTrace();}}//找到链表前一个的位置private ListNode searchPrev(int index) {ListNode cur this.head;int count 0;while (count ! index - 1) {cur cur.next;count;}return cur;}public class IndexException extends RuntimeException{public IndexException(String e) {super(e);}
}6contains方法
查找是否包含关键字key是否在单链表当中遍历一遍链表有该元素就返回true没有就返回false代码如下
public boolean contains(int key) {ListNode cur this.head;while (cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}
7remove删除第一个key值节点的方法
删除一个节点先要判断该链表为不为空为空就退出不为空看要删的节点是不是头结点是头结点就直接把头结点改成头结点的next域要删除的节点可能在中间就要扎到要删除节点的前一个节点把前一个节点的next域指向要删除节点的next域就好了代码如下
public void remove(int key) {if(this.head null) {//一个节点都没有无法删除return;}if(this.head.val key) {this.head this.head.next;return;}ListNode cur findPrev(key);if(cur null) {System.out.println(没有要删除的点);} else {ListNode del cur.next;cur.next del.next;}}private ListNode findPrev(int key) {ListNode cur this.head;while (cur.next ! null) {if(cur.next.val key) {break;}cur cur.next;}return cur this.head ? null : cur;}
执行结果如下 8removeAllKey删除所有值为key的方法
如果头结点是空的就不用进行下面操作直接返回。
两个节点一个的前节点一个是前节点的后一个节点遍历后一个节点判断后一个节点的val值是不是key是key就把前一个节点的next域指向后一个节点的next域后一个节点向后移没有命中后一个节点key这条件前一个节点和后一个节点都要往后移动一步。
最后还要判断头结点的val值是否等于key值是就要把head标记成head的next域。
代码入如下
public void removeAllKey(int key) {if(this.head null) {return;}ListNode prev this.head;ListNode cur this.head.next;while (cur ! null) {if(cur.val key) {prev.next cur.next;cur cur.next;} else {cur cur.next;prev prev.next;}}if(this.head.val key) {this.head this.head.next;}}
执行结果如下 9clear方法
清除所有节点有两种解决方案第一种是直接把头结点设为空这种方法比较暴力第二种是把每个节点的next域设为空同时val也要设为空因为这里的val类型是int所以就设置不了空了最后再把head节点设为空代码如下 public void clear() {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;cur.next null;cur curNext;}head null;}
执行结果如下 四、最终代码
public class MyLinkedList implements Ilist{public ListNode head;static class ListNode{int val;ListNode next;public ListNode(int val) {this.val val;}}public void createList() {ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;}Overridepublic void addFirst(int data) {ListNode node new ListNode(data);if(this.head null) {this.head node;} else {node.next this.head;this.head node;}}Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(this.head null) {this.head node;} else {ListNode cur this.head;while (cur.next ! null) {cur cur.next;}cur.next node;}}Overridepublic void addIndex(int index, int data) {try {if(index 0 || index size()) {throw new IndexException(下标异常,下标: index);} else {if(index 0) {//头插addFirst(data);return;}if (index size()) {//尾插addLast(data);return;}ListNode node new ListNode(data);ListNode cur searchPrev(index);node.next cur.next;cur.next node;}} catch (IndexException e) {e.printStackTrace();}}//找到链表前一个的位置private ListNode searchPrev(int index) {ListNode cur this.head;int count 0;while (count ! index - 1) {cur cur.next;count;}return cur;}Overridepublic boolean contains(int key) {ListNode cur this.head;while (cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}Overridepublic void remove(int key) {if(this.head null) {//一个节点都没有无法删除return;}if(this.head.val key) {this.head this.head.next;return;}ListNode cur findPrev(key);if(cur null) {System.out.println(没有要删除的点);} else {ListNode del cur.next;cur.next del.next;}}private ListNode findPrev(int key) {ListNode cur this.head;while (cur.next ! null) {if(cur.next.val key) {break;}cur cur.next;}return cur this.head ? null : cur;}Overridepublic void removeAllKey(int key) {if(this.head null) {return;}ListNode prev this.head;ListNode cur this.head.next;while (cur ! null) {if(cur.val key) {prev.next cur.next;cur cur.next;} else {cur cur.next;prev prev.next;}}if(this.head.val key) {this.head this.head.next;}}Overridepublic int size() {int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}Overridepublic void clear() {ListNode cur this.head;while (cur ! null) {ListNode curNext cur.next;cur.next null;cur curNext;}head null;}Overridepublic void display() {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}
}//自定义异常类
public class IndexException extends RuntimeException{public IndexException(String e) {super(e);}
}点个赞再走吧谢谢谢谢谢
