石家庄网站外包公司做机械一般做那个外贸网站

当前位置： 首页 > news >正文

石家庄网站外包公司,做机械一般做那个外贸网站,个人微信小程序开发,公司建设网站需求分析1. 链表的概念 链表用于存储一系列元素#xff0c;由一系列节点组成#xff0c;每个节点包含两部分#xff1a;数据域和指针域。 数据域#xff1a;用于存储数据元素 指针域#xff1a;用于指向下一个节点的地址#xff0c;通过指针将各个节点连接在一起#xff0c;形…1. 链表的概念 链表用于存储一系列元素由一系列节点组成每个节点包含两部分数据域和指针域。 数据域用于存储数据元素 指针域用于指向下一个节点的地址通过指针将各个节点连接在一起形成一个链式结构。 注意 链表在逻辑上是连续的空间上并不是连续的 根据指针的连接方式链表可以分为单向链表和双向链表 注意 单向链表和双向链表的结点存在差异

1. 单向链表 单向链表是链表的一种它的每个节点除了存储数据外还包含一个指针指向下一个节点地址 2.1 单向列表的节点 每个节点只有一个指针指向下一个节点。 最后一个节点的指针指向null表示链表结束。 代码实现 class ListNode{int val;ListNode next;//next指向新的节点public ListNode(int val) {this.val val;}} 注意  结点一般都是从堆上申请出来每次在堆上申请的空间按照一种策略来进行分配多次申请出来的空间可能连续也可能不连续 2.2 链表的创建
2. 创建一个节点 2.创建第二个节点让第一个节点的指针域存放第一个节点的地址以此类推可以创建出链表 代码实现 public void createList(){//创建节点ListNode listNode new ListNode(15);ListNode listNode1 new ListNode(56);ListNode listNode2 new ListNode(45);ListNode listNode3 new ListNode(88);//节点连接listNode.next listNode1;listNode1.next listNode2;listNode2.next listNode3;this.head listNode;} 注意 不要忘记标注链表的头节点当输出头节点时会输出整个链表的数据 2.3 链表的种类 2.4 链表的基本操作 2.4.1 增加 1头插法 主要操作 将新创建的节点的指针域更改为头节点的地址 将头节点的位置进行改变 public void addFirst(int data){//代码不能交换//必须先绑定信息ListNode listNode new ListNode(data);listNode.next head;head listNode;} 注意代码的先后顺序不能颠倒否则获取不到listNode.next的位置  2尾插法 主要操作 将最后一个节点的指针域指向新节点的地址  特殊情况 链表内没有一个节点那么让新节点成为头节点 代码实现 public void addLast(int data){ListNode listNode new ListNode(data);ListNode cur head;if(curnull){head listNode;return ;}while(cur.next!null){//关注next的指向,找到最后一个节点cur cur.next;}cur.next listNode;} 3固定位置插入 主要操作 找到要插入位置的前一个位置cur让新节点的指针域指向要插入位置的旧节点让cur指针域指向新节点的地址 注意第二步和第三步不能交换位置如果交换会导致cur的位置发生改变导致无法找到要插入位置的地址 代码实现 public void addIndex(int index,int data){if(index0||indexsize()){System.out.println(位置有问题);return;}if(index 0){addFirst(data);return;}if(index size()){addLast(data);return ;}ListNode cur head;int count 0;ListNode listNode new ListNode(data);while(countindex-1){cur cur.next;count;}//不能互换位置listNode.next cur.next;cur.next listNode;}注意 不要忘记检查插入的位置是否合法 如果插入的位置为0那么意味着头插法位置为元素的长度那么就是尾插法 2.4.2 删除 1删除第一个出现的元素 主要步骤 找到你要删除元素的前一个节点找到你要删除的节点进行删除操作 代码实现 public void remove(int data){if(head null){return;}if(head.val data){head head.next;return;}//1.找到你要删除的前一个节点ListNode cur head;int count 0;while(cur.next!null){if(cur.next.val data){break;}count;cur cur.next;}//找到要删除的节点ListNode del head;int delindex 0;while (del!null){if(del.val data){break;}delindex;del del.next;}//删除操作cur.next del.next;}注意删除的具体操作就是删除节点的前一个节点的指向发生改变指向删除元素的指向 2删除出现的所有元素 主要步骤 初始化两个节点cur节点进行判断值是否相同previous是cur节点的前一个结点方便进行删除操作进行遍历链表找到相同的值则进行删除操作反之将两个节点都向后移动一位 代码实现 if(head null){return;}ListNode cur head.next;ListNode previous head;while(cur!null){if(cur.valdata){previous.next cur.next;cur cur.next;}else{previous cur;//注意小心写成 previous.next cur;//错误cur cur.next;}}if(head.val data){head head.next;}} 注意不要忘记对头节点进行判断 2.4.3 查看 1查看链表是否存在元素 public boolean contains(int value){ListNode cur head;while(cur!null){if(cur.valvalue){return true;}cur cur.next;}return false;} 主要步骤 采用遍历的形式如果找到元素则返回true反之返回false 2.4.4 获取链表长度 int size(){int count 0;ListNode cur head;while (cur!null){cur cur.next;count;}return count;} 2.4.5 清空链表 void clear(){ListNode cur head;ListNode curNext ;while(cur!null){curNext cur.next;cur.next null;cur curNext;}head null;} } 注意 遍历链表逐个释放节点的引用让每个节点不再被引用
3. 快慢指针 思想通过使用两个速度不同的指针快指针和慢指针来遍历数据结构从而实现特定的功能 注意本质就是利用指针的移动速度差异来解决问题 常见的解决情况 1找出中间的节点 ListNode findListNode(Text_2 list){ListNode mid head;if(head null){return null;}if(head.next null){return head;}int count size(list);int midCount count/2;while (midCount0){mid mid.next;midCount–;}return mid;} 这是解决这种问题我们第一个想到的方法需要遍历两次链表获取长度和中间节点 复杂度高下面是我们引用了快慢指针 ListNode findListNode1(){ListNode fast head;ListNode slow head;while(fast!nullfast.next!null){//不能交换fast fast.next.next;slow slow.next;}return slow;} 核心思想使用快慢双指针快的是慢的二倍那么快的到了慢的一定就在中间 2找出倒数第k个节点 ListNode findListNode(int k){if(head null){return null;}if(k0||ksize()){System.out.println(k取值不对);return null;}ListNode slow head;ListNode fast head;int count k-1;while (count0){fast fast.next;count–;}while(fast!nullfast.next!null){fast fast.next;slow slow.next;}return slow;} 核心思想快的比慢的先走了k-1个然后每次都移动一个 那么快的到了满的就是倒数第k个. 先走k-1个因为下标从0开始
4. 双向链表 双向链表是链表的一种它的每个节点除了存储数据外还包含两个指针一个指向前一个节点另一个指向下一个节点 4.1 双向列表的节点 注意 由于有前驱指针删除和插入操作更高效。 每个节点需要额外存储一个指针因此比单向链表占用更多内存。 可以从头节点向后遍历也可以从尾节点向前遍历。 代码实现 class ListNode{int val;ListNode prev;ListNode next;public ListNode(int val) {this.val val;} } 4.2 LinkedList 在 Java 中LinkedList是java.util 包中的一个类LinkedList的底层使用了双向链表 4.3 LinkedList的使用 4.3.1 LinkedList的构造 1无参构造 //调用无参构造ListInteger list new LinkedList(); 2利用Collection构建 ListInteger list1 new LinkedList();list1.add(1);list1.add(2);list1.add(3);System.out.println(list1);ListInteger list2 new LinkedList(list1);list2.add(2);System.out.println(list2); 注意会继承传入实例对象的所有元素并且元素的顺序也会保持一致 4.3.2  LinkedList的常用API boolean add(E e) 尾插 void add(int index, E element) 在index位置添加元素 boolean addAll(Collection? extends E c) 将c中的所有元素插入进来 E remove(int index) 删除index下标的元素 boolean remove(Object o) 删除一个o元素 E get(int index) 获得index下标的元素 E set(int index, E element) 将index下标的元素更改为element void clear() 清空顺序表 boolean contains(Object o) 查看是否有元素o int indexOf(Object o) 获取第一个元素o的下标 int lastIndexOf(Object o) 获取最后一个元素o的下标 ListE subList(int fromIndex, int toIndex) 截取顺序表的一部分
   1增加 public class Add {public static void main(String[] args) {//尾插法LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println(list);//插入固定位置LinkedListInteger list1 new LinkedList();list1.add(0,1);list1.add(0,6);list1.add(1,9);System.out.println(list1);//尾插所有元素Integer[] array {9,99,999};list.addAll(Arrays.asList(array));System.out.println(list);} }2删除 public class Remove {public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);//删除下标的数list.remove(2);System.out.println(list);//删除第一个出现的数list.remove(new Integer(2));System.out.println(list);} }3修改 public class Set {public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);list.set(1,999);System.out.println(list);} }4获取 public class Get {public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);int x list.get(2);System.out.println(x);} }5清空 public class Clear {public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);list.clear();System.out.println(list);} }6查找 public class Contains {public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3); // 判断元素是否在表中Boolean x list.contains(2);System.out.println(x); // 返回第一个元素所在的下标int a list.indexOf(2);System.out.println(a); // 返回最后一个元素所在的下标int b list.lastIndexOf(2);System.out.println(b);} }7截取 public class Sublist {public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);list.add(6);list.add(9);// LinkedListInteger list1 new LinkedList(list.subList(1,4));//创建新的对象进行操作不会影响原来列表的数据//subList返回值是List类型ListInteger list1 list.subList(1,4);list1.add(999);list1.add(888);list1.set(0,111);System.out.println(list1);System.out.println(list);} }4.3.3 LinkedList的遍历 1for循环遍历 //1.for (int i 0; i list.size(); i) {System.out.print(list.get(i) );}System.out.println(); 2for-each遍历 //2for (int x : list){System.out.print(x );} 3使用迭代器 正向遍历 //3IteratorInteger iterator list.listIterator();//传数据while (iterator.hasNext()){System.out.print(iterator.next() );}System.out.println(); 反向遍历 //4ListIteratorInteger listIterator list.listIterator(list.size());while (listIterator.hasPrevious()){System.out.print(listIterator.previous() );}System.out.println(); 注意 从前往后while循环中的判断条件表示是否存在下一个元素如果存在则获取迭代器的下一个元素并输出因为 next 方法所以在每次调用后进行移动1位
5. ArrayList和LinkedList的区别 差别 ArrayList LinkedList 底层实现 基于动态数组实现 基于双向链表实现 访问效率 随机访问效率高 随机访问效率低 插入和删除效率 尾部插入和删除效率高 中间或头部插入和删除效率低 任意位置插入和删除效率高 内存占用 内存占用较少因为只需要存储数据和数组容量。 可能存在内存浪费因为数组会预留一定的容量 内存占用较多因为每个节点需要存储数据以及前后指针。
   总结 ArrayList  适合频繁访问元素的场景例如随机读取数据适合元素数量相对固定的场景。 LinkedList 适合频繁插入和删除的场景例如实现栈、队列适合元素数量动态变化的场景。