在线网站建设联系人,wap娃派手机信息网,美食网站 怎么做,锕锕锕锕锕锕锕好湿免费网址꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN … ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好我是xiaoxie.希望你看完之后,有不足之处请多多谅解让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶个人主页xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 系列专栏xiaoxie的JAVA系列专栏——CSDN博客●ᴗσσணღ*我的目标:团团等我( ◡̀_◡́ ҂) ( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞 收藏⭐️ 留言关注互三必回! 目录
编辑一.顺序表
1.底层实现
2.构造方法
3.常用方法
4.Arrays的遍历方法
编辑5.实战演示 一.顺序表
1.底层实现
首先我们要清楚数据结构是一门逻辑十分清晰的学科所以我们需要清楚的认识到每个结构的底层是什么这样才能更好的掌握这个结构。 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成 数据的增删查改。 2.构造方法 在集合框架中 ArrayList 是一个普通的类实现了 List接口并且ArrayList是一个泛型类 而ArrayList的构造方法如下所示 public class Text {public static void main(String[] args) {//无参ListInteger list new ArrayList();//指定顺序表初始容量ListInteger list1 new ArrayList(20);list1.add(1);list1.add(11);//ArrayList(Collection? extends E c) 利用其他 Collection 构建 ArrayListListInteger list2 new ArrayList(list1);}
}3.常用方法 ArrayList是一个普通的类实现了List接口所以它实现了许多接口内的方法博主现在为大家列举出一些常用的方法 ListInteger list new ArrayList();//尾插入元素list.add(1);list.add(12);list.add(11);//指定位置插入参数为 位置 和 元素list.add(2,3);//顺序表长度list.size();//删除指定位置元素list.remove(2);//是否包含某个元素list.contains(4);//截取部分 listlist.subList(0,1);//获取下标 index 位置元素list.get(2);//将下标 index 位置元素设置为 elementlist.set(3,9);//返回第一个 o 所在下标list.indexOf(8);//返回最后一个 o 的下标list.lastIndexOf(8);4.Arrays的遍历方法 1.直接输出 ListInteger list new ArrayList();//尾插入元素list.add(1);list.add(12);list.add(11);System.out.println(list); 2.for循环和for-each
ListInteger list new ArrayList();//尾插入元素list.add(1);list.add(12);list.add(11);System.out.println(for循环遍历);for (int i 0; i list.size(); i) {System.out.print(list.get(i) );}System.out.println();System.out.println(for-each循环遍历);for (Integer x:list) {System.out.print(x );} 3.使用迭代器
ListInteger list new ArrayList();//尾插入元素list.add(1);list.add(12);list.add(11);System.out.println(迭代器正序输出);IteratorIntegerit list.iterator();while (it.hasNext()) {System.out.print(it.next() );}System.out.println();System.out.println(迭代器逆序输出);ListIterator Integer it1 list.listIterator(list.size());while (it1.hasPrevious()) {System.out.print(it1.previous() );}}
5.实战演示
杨辉三角 力扣的118题难度不大感兴趣的朋友可以去尝试一下
解答代码如下
/*11 1 1 2 11 3 3 11 4 6 4 1 由图可知每一行的第一个为1最后一个也为一中间部分等于上一行的前一个加上上一行同一列的一个并且最后一个也为一。
*/
class Solution {public ListListInteger generate(int numRows) {ListInteger list new ArrayList();ListListInteger ans new ArrayList();list.add(1);//第一行ans.add(list);for(int i 1;i numRows;i) {ListInteger temp new ArrayList();temp.add(1);//每一行的第一个都为一ListInteger row ans.get(i-1);//上一行for(int j 1; j i;j) {int x row.get(j)row.get(j-1);//中间部分为上一行的前一个加上上一行同一列的一个temp.add(x);}temp.add(1);//一行的最后一个元素也为1ans.add(temp);}return ans;}
}
以上是博主解答这题的思路和代码时间复杂度为On^2如果你有更好的方法或者是不懂的地方都可以私聊博主大家一起交流进步
二.链表
1.底层实现 链表是一种 物理存储结构上非连续 存储结构数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的它的结构如下 当然链表的结构不仅仅是这一种其他还有1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 虽然有这么多的链表的结构但是我们重点掌握两种 : 无头单向非循环链表 结构简单 一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 如 哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。 无头双向链表 在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。 2.无头单向非循环链表
无头单向非循环链表是一种数据结构其特点是没有头节点、只有一个指向第一个节点的指针而且最后一个节点的指针为空NULL形成一个单向链表的尾部。这意味着如果需要查找第一个节点必须从指向第一个节点的指针开始遍历链表。此外非循环链表是一个单向链表从第一个节点开始一直到最后一个节点而最后一个节点指向空NULL这样就可以避免链表中的死循环问题。
3.无头双向非循环链表
无头双向非循环链表是一种数据结构它由多个节点组成每个节点有两个指针一个指向前一个节点一个指向后一个节点。和单向链表不同的是双向链表可以向前和向后遍历而且插入和删除节点的操作比较方便。
无头表示链表没有头节点也就是第一个节点就是链表的起始节点。非循环表示链表没有环也就是最后一个节点的指针指向 NULL。
在无头双向非循环链表中我们可以从任意一个节点开始遍历也可以逆序遍历整个链表。双向链表比单向链表多了一个指针所以它在一些场景下比单向链表更加方便比如需要频繁地插入和删除节点时。但是它也需要更多的内存空间来存储指针。
4.顺序表和链表之间的区别 顺序表和链表是两种数据结构它们的主要区别在于存储方式和操作效率不同 存储方式不同顺序表使用一组连续的存储单元存储数据而链表则使用指针将一组零散的存储单元串联起来。 随机访问效率不同顺序表通过下标可以直接访问任意位置的元素时间复杂度为O(1)但插入和删除操作需要移动数据时间复杂度为O(n)。而链表不能通过下标直接访问元素插入和删除操作只需要修改指针时间复杂度为O(1)但是随机访问需要遍历整个链表时间复杂度为O(n)。 空间利用率不同顺序表预先分配存储空间大小固定当存储空间不够时需要重新分配内存可能浪费内存。而链表通过动态分配内存只在需要时才分配所需的存储空间空间利用率较高。
总之应根据实际需求选择合适的数据结构如果需要频繁随机访问可以选择顺序表如果需要频繁插入和删除可以选择链表。
5.链表面试题
1.给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 NULL 链接
public class Solution {// 定义一个方法detectCycle输入参数为链表头节点head返回值类型为ListNode链表节点public ListNode detectCycle(ListNode head) {// 如果链表为空或只有一个元素则没有环直接返回nullif(head null || head.next null) {return null;}// 初始化两个指针fast和slow都指向链表头节点ListNode fast head;ListNode slow head;// 使用快慢指针进行遍历while(fast ! null fast.next ! null) {// 慢指针每次前进一步slow slow.next;// 快指针每次前进两步fast fast.next.next;// 如果快慢指针相遇则说明存在环if(slow fast) {break;}}// 如果快指针遍历到链表末尾说明不存在环返回nullif(fast null || fast.next null) {return null;}// 重新设置快指针fast到链表头节点慢指针slow保持在相遇点fast head;// 当快慢指针再次相遇时相遇点即为环的起点while(slow ! fast) {slow slow.next;fast fast.next;}// 返回环的起点return fast;}
}
2.链表的回文结构链接
public class PalindromeList {// 定义一个方法chkPalindrome输入参数为链表头节点head返回值类型为布尔值true表示是回文链表false表示不是public boolean chkPalindrome(ListNode head) {// 如果链表为空则直接返回true空链表是回文链表if(head null ) {return true;}// 使用快慢指针找到链表的中间结点ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next; // 快指针每次前进一步slow slow.next; // 慢指针每次前进一步}// 翻转链表后半部分ListNode cur slow.next;while(cur ! null) {ListNode curnext cur.next;cur.next slow;slow cur;cur curnext;}// 判断翻转后的链表与原链表前半部分是否相等while(head ! slow) {if(head.val ! slow.val) { // 如果两个节点的值不相等则说明不是回文链表return false;}if(head.next ! slow) { // 奇数情况下已经比较完所有节点可以提前结束循环return true;}head head.next; // 头节点向后移动一位slow slow.next; // 反转后的尾节点向前移动一位}// 遍历结束后没有发现不相等的节点说明是回文链表return true;}
}
3.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。链接 public class Partition {// 定义一个方法partition输入参数为链表头节点head和整数x返回值类型为ListNode链表节点public ListNode partition(ListNode head, int x) {// 如果链表为空则直接返回nullif(head null) {return null;}// 初始化两个指针de和dx用于记录小于x的元素链表的尾节点和当前节点ListNode de null;ListNode dx null;// 初始化两个指针pe和px用于记录大于等于x的元素链表的尾节点和当前节点ListNode pe null;ListNode px null;// 初始化一个指针cur指向链表的头节点ListNode cur head;// 遍历链表中的每个节点while(cur ! null) {// 如果当前节点的值小于xif(cur.val x) {// 如果小于x的元素链表尚未创建则将当前节点设置为头节点和尾节点if(de null) {de cur;dx cur;}else { // 否则将当前节点添加到小于x的元素链表的末尾dx.next cur;dx dx.next;}}else { // 如果当前节点的值大于等于x// 如果大于等于x的元素链表尚未创建则将当前节点设置为头节点和尾节点if(pe null) {pe cur;px cur;}else { // 否则将当前节点添加到大于等于x的元素链表的末尾px.next cur;px px.next;}}// 指针cur向后移动一位cur cur.next;}// 如果不存在小于x的元素则直接返回大于等于x的元素链表if(dx null) {return pe;}// 将大于等于x的元素链表接到小于x的元素链表的末尾dx.next pe;// 如果存在大于等于x的元素则将其尾节点的next指针置为nullif(pe ! null) {px.next null;}// 返回小于x的元素链表的头节点return de;}
}
三.结语
数据结构一门逻辑十分严谨的一门学科而顺序表和链表都是十分基础的结构也是后续学习的基础所以应该要多花时间去搞清楚它的底层好了本文到这里就结束了感谢您的阅读祝您一天愉快
