网站管理系统改不了的,wordpress博客被书为什么还,建建建设网站,很多网站的导航条都设置为7到9认识LinkedList LinkedList就是一个链表#xff0c;它也是实现List接口的一个类。LinkedList就是通过next引用将所有的结点链接起来#xff0c;所以不需要数组。LinkedList也是以泛型的方法实现的#xff0c;所以使用这个类都需要实例化对象。 链表分为很多种#xff0c;比…认识LinkedList LinkedList就是一个链表它也是实现List接口的一个类。LinkedList就是通过next引用将所有的结点链接起来所以不需要数组。LinkedList也是以泛型的方法实现的所以使用这个类都需要实例化对象。 链表分为很多种比较常用的就两种单链表单向、不带头、非循环和双链表双向、不带头、非循环后面会模拟实现。下面是顺序表和链表的区别 模拟实现LinkedList
单链表 首先需要创建结点但是它比顺序表多了一个next引用可以通过next引用来访问下一个结点不再需要通过连续地址访问首先先创建结点这个类 然后再实现增删查改等这些方法
链表长度、遍历链表、头插法、尾插法、任意位置插入、查找关键字key是否在链表中 、删除第一次出现关键字为key的节点、删除所有值为key的节点、清空。
public class MySingle {static class ListNode{private int val;private ListNode next;public ListNode(int val){this.val val;}}private ListNode head;//头插法public void addFirst(int data){ListNode node new ListNode(data);node.next head;head node;}//尾插法public void addLast(int data){ListNode node new ListNode(data);if (head null){head node;}else {ListNode cur head;while (cur.next ! null) {cur cur.next;}cur.next node;}}//任意位置插入public void addIndex(int index,int data){if (index 0 || index size()){throw new IndexOutOfException(位置不合法);}if (index 0){addFirst(data);return;}ListNode node new ListNode(data);ListNode cur head;while (index - 1 ! 0){cur cur.next;index--;}//将index位置前后两个节点和新结点联系起来node.next cur.next;cur.next node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur head;while (cur ! null){if (cur.val key){return true;}}return false;}public ListNode keyPre(int key){ListNode cur head;while (cur.next ! null){if (cur.next.val key){return cur;}cur cur.next;}return null;}//删除第一次出现关键字为key的节点public void remove(int key){if (head null){return;}if (head.val key){head head.next;return;}//找到key结点的前一个结点ListNode pre keyPre(key);ListNode del pre.next;pre.next del.next;}//删除所有值为key的节点public void removeAllKey(int key){ListNode pre head;ListNode cur head.next;while (cur ! null){if (cur.val key){pre.next cur.next;cur cur.next;}else{pre pre.next;cur cur.next;}}if (head.val key){head head.next;}}//得到单链表的长度public int size(){int count 0;ListNode cur head;while (cur ! null){count;cur cur.next;}return count;}public void display(){ListNode cur head;while (cur ! null){System.out.print(cur.val );cur cur.next;}System.out.println();}
}
双链表LinkedList LinkedList其实就是一个双链表 它既可以访问前驱又可以访问后继所以可以快速插入和删除。下面是LinkedList模拟实现比较难的就是插入和删除
public class MyLinkedList {static class ListNode{private int val;private ListNode prev;private ListNode next;public ListNode(int val){this.val val;}}public ListNode head;public ListNode tail;//头插法public void addFirst(int data){ListNode node new ListNode(data);if (head null){head node;tail node;}else {head.prev node;node.next head;head node;}}//尾插法public void addLast(int data){ListNode node new ListNode(data);if (tail null){head node;tail node;}else{tail.next node;node.prev tail;tail node;//tail tail.next;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if (index 0 || index size()){throw new IndexOutofBoundException(index位置不合理);}ListNode node new ListNode(data);ListNode cur head;while (index 0){cur cur.next;index--;}node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur head;while (cur ! null){if (cur.val key){return true;}cur cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if (head null){return ;}ListNode cur head;while(cur ! null ) {if (cur.val key){if (cur.next null cur.prev null){head null;tail null;return;}if (cur.prev null) {head cur.next;cur.next.prev null;return;}if(cur.next null){tail cur.prev;cur.prev.next null;return;}cur.prev.next cur.next;cur.next.prev cur.prev;return;}else{cur cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){if (head null){return ;}ListNode cur head;while(cur ! null ) {if (cur.val key){if (cur.next null cur.prev null){head null;tail null;}else if (cur.prev null) {head cur.next;cur.next.prev null;}else if(cur.next null){tail cur.prev;cur.prev.next null;}else {cur.prev.next cur.next;cur.next.prev cur.prev;}cur cur.next;}else{cur cur.next;}}}//得到单链表的长度public int size(){ListNode cur head;int size 0;while (cur ! null){size;cur cur.next;}return size;}//清空public void clear(){ListNode cur head;while(cur ! null){ListNode curNext cur.next;cur.prev null;cur.next null;cur curNext;}head null;tail null;}//遍历public void display(){ListNode cur head;while (cur ! null){System.out.print(cur.val );cur cur.next;}System.out.println();}
}
LinkedList的创建
构造一个对象可以无参构造较为常用在其里初始化一个数组。 LinkedList的遍历 遍历的方法和ArrayList里一样三种for循环、增强for循环、迭代器。这两个遍历方法都是一样的就不重复叙述。https://blog.csdn.net/2402_84815218/article/details/144038207?spm1001.2014.3001.5502
LinkedList常用方法 这些方法和ArrayList中的方法差不多都一样只是实现的过程不一样。这里我就举几个例子 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(12);//尾插进入list.add(23);System.out.println(list);//【1223】
// list.add(3, 100);//插入到第index位置但是该list中没有第三个位置
// System.out.println(list);System.out.println(list.get(1));//得到1位置元素 23list.set(1,100);//更新1位置的元素System.out.println(list.get(1));// 100list.remove(1);//删除1位置元素list.clear();//清空链表System.out.println(list);//【】}
ArrayList与LinkedList的区别 简而言之就是LinkedList的插入和删除的复杂度高而ArrayList的可能需要移动n次数据所以应用根据应用场景来判断使用哪一种。
