个人企业网站,公司视频宣传片,公司做网站的费用的会计分录,苏州工业园区文章目录 链表一、 链表的概念1.概念2. 结构 二、MySingleList的实现1 .定义内部类2 .创建链表3. 遍历链表并打印4.查找单链表中是否包含关键字key5.得到链表的长度6.头插法7. 尾插法8.任意位置插入8.删除结点清空 链表
顺序存储#xff1a;顺序表/ArrayList
优点#xff1… 文章目录 链表一、 链表的概念1.概念2. 结构 二、MySingleList的实现1 .定义内部类2 .创建链表3. 遍历链表并打印4.查找单链表中是否包含关键字key5.得到链表的长度6.头插法7. 尾插法8.任意位置插入8.删除结点清空 链表
顺序存储顺序表/ArrayList
优点给定下标的时候查找速度快 o(1)缺点插入和删除时要移动元素o(n) 、每次扩容会浪费资源
由于ArrayList的缺点我们引入链式存储链表
一、 链表的概念
1.概念 链表在物理层面是非连续的存储结构在逻辑上是连续的通过引用链接次序来实现它的逻辑顺序链表由一个个结点组成结点从堆上申请一个结点起码包含两个域val域存储数组、next域存储下一个结点的地址
2. 结构 链表由多种结构由头、无头、单向、双向、循环、非循环 排列组合后有八种重点了解无头单向非循环链表和无头双向链表 二、MySingleList的实现
无头单向非循环链表的实现
1 .定义内部类
public class MySingleList {//链表是由一个一个的结点所组成的可以把Node定义成一个内部类static class Node {public int val;//存储的数据public Node next;//存储下一个结点的地址public Node(int val) {//先不设置next,创建一个新的结点时还不知道下一个结点是什么this.val val;}}
}
链表是由一个个的结点所组成的可以把Node定义成一个内部类
定义一个val变量存储数据定义一个Node类型的next变量存储下一个结点的地址 public Node head;//代表当前链表的头结点的引用head 代表当前链表的头结点的引用
因为现在写的是不带头结点的单链表通过一个变量head来引用当前链表的头结点head引用哪个结点哪个就是当前链表的头结点
2 .创建链表
public void creatList(){//创建一个链表Node node1 new Node(12);Node node2 new Node(86);Node node3 new Node(33);Node node4 new Node(45);node1.next node2;node2.next node3;node3.next node4;headnode1;//创建头结点}创建各个结点给定val值每个结点的next依次引用下一个结点的地址 确定头结点head引用node1所引用的地址 3. 遍历链表并打印
public void disPlay() {//不要改变headNode cur head;//定义一个cur让cur移动head不动//链表遍历完headnull//遍历到尾部不打印最后一个head.nextnullwhile (cur!null){System.out.print(cur.val );cur cur.next;}System.out.println();}1.通过cur来代替head保证head不会发生改变 2.循环的判断依据是cur!null这样能遍历完整 cur.next!null会少打印最后一个 4.查找单链表中是否包含关键字key
public boolean contains(int key) {Node cur head;while (cur ! null) {//当cur为空时遍历完if (cur.val key) {return true;}cur cur.next;//cur向后移动}return false;}5.得到链表的长度 public int size(){int count 0;Node cur head;while (cur!null) {//遍历一遍链表 o(n)count;curcur.next;}return count ;}遍历数组直到cur为null跳出循环说明已经走完整个链表返回记录的次数 6.头插法 public void addFirst(int data){Node node new Node(data);//新建一个结点node.nexthead;head node;} 1.创建新的结点 2.将新结点的next域存放原本头结点的地址值 3.让新结点成为新的头结点 这样就完成了头插法的实现 7. 尾插法 public void addList(int data) {Node node new Node(data);if (head null) {//判断头结点为空的情况head node;//让新建的结点成为头节点return;//}Node cur head;//让cur代替headwhile (cur.next ! null) {cur cur.next;}//当cur的next为null时找到了最后一个结点//找到最后一个结点后插入node结点cur.next node;}1.创建一个新结点 2.判断头结点是否为空 3.遍历链表找到当前最后一个结点 4.将新结点插到末尾 链表的插入只是修改指向 8.任意位置插入 public void addIndex(int index, int data) throws IndexOutOfException {checkIndex(index);//先检查index的值是否合法if (index 0) {//如果index0调用头插法addFirst(data);return;}if (index size()) {//如果index的值为链表长度调用尾插法addList(data);return;}Node cur findIndexSubOne(index);//找到index的前一个元素Node node new Node(data);node.next cur.next;cur.next node;}private void checkIndex(int index) {if (index 0 || index size()) {throw new IndexOutOfException(index位置不合法);}}//走index-1步返回当前索引的地址private Node findIndexSubOne(int index) {Node cur head;int count 0;while (count ! index - 1) {cur cur.next;count;}return cur;} 1.调用checkIndex方法先检查index的值是否合法,不合法抛出异常 2.判断索引如果是0调用头插法如果等于链表长调用尾插法 3.调用findIndexSubOne方法找到index的前一个节点返回地址值 4.创建一个新结点使新结点的next域的值等于前一个结点next域的值 5.再让前一个结点的next域引用新结点的地址值。 8.删除结点
删除第一次出现关键字为key的结点 public void remove(int key) {if (head null) {//判断是否是空节点return; //一个结点都没有}if (head.val key) {//如果当前头结点的元素等于要删除的元素head head.next;//头结点向后移动return;}Node cur searchPrev(key);//找到key的前驱结点if (cur null) {//没有要删除的keyreturn;}Node del cur.next;//要删除的结点cur.next del.next;//or cur.next cur.next.next;}private Node searchPrev(int key) {//找到key的前一个结点Node cur head;while (cur.next ! null) { //cur.nextnull,说明cur已经走到最后一个结点if (cur.next.val key) {//如果cur下一个结点的值等于keyreturn cur;//找到key的前一个结点}cur cur.next;}return null;//没有你要删除的结点}1.先定义searchPrev方法遍历链表如果cur的下一个结点的值key,cur就为key的前驱结点 2.判断如果头结点为空链表中没有元素直接返回 3.如果头结点的值就是要删除的元素头结点后移直接返回 4.都不是进入searchPrev方法返回前驱结点cur 5.如果返回的curnull说明遍历完链表没有要删除的元素 6.要删除的结点del就是cur的下一个结点 7.让cur结点的next域引用del的下一个结点的地址 完成删除 删除所有值为key的节点 public void removeAllKey(int key) {if (head null) {//如果头结点为空直接返回return ;}Node prev head;Node cur head.next;while (cur ! null) {if (cur.val key) {prev.next cur.next;//cur cur.next;} else {prev cur;//cur cur.next;}cur cur.next;}if (head.val key) {//最后处理头结点//如果头结点的值等于key,头结点后移head head.next;}}1.判断头结点是否为空 2.设置prev为头结点cur为下一个结点头结点key的情况最后考虑 3.遍历链表直到curnull为止 4.如果cur的值等于key,prev的next域引用cur下一个结点的地址cur后移一位 5.否则prev移动到cur,cur后移一位 6.最后处理头结点如果头结点刚好等于key,将头结点后移一位。 清空 public void clear(){//清空让链表中所有的结点都不被引用head null;}清空让链表中所有的结点都不被引用,head置为空 点击移步博客主页欢迎光临~
