2023年6月29日发(作者：)

在单链表写⼊⼀组数据代码_数据结构之链表的实现前⾔学了数据结构之后，就⽤编程语⾔去实现它，这样理解才通透。同时地，学会刷题也是很重要，例如现在⼈尽皆知的leetcode。 我的⽬标就是进⼤⼚，⽽必须要过的⼀关就是数据结构，慢慢学吧~ ⾏百⾥者半九⼗。我实现数据结构的代码是java，⽤什么语⾔不重要，主要是思路正确就可以了。所以你想学习c、c++也是⼀样的。然后，这个博客系列是给⼩⽩看的，所以我有⼀些阅读建议：我会给出实现思路，先跟着我⼀起思考，虽然有些地⽅说的有些拗⼝，没办法，这是写作的缺点之⼀，所以要理解每⼀个地⽅说的概念后再往下，不然发现看不懂⾃然⽽然就“收藏夹吃灰”了看懂了不⼀定会，要⾃⼰实现⼀下，你会发现巨多的坑等着你不要急，慢慢来，你可以学会的(真的)上⼀节我们提到了链表，那么我们这⼀篇就来实现其结构。链表的定义：1)链表是以节点的⽅式来存储是链式存储2)每个节点包含data域(存放的数据), next域:指向下⼀个节点，当next指向null时，可以表明才链表元素是尾结点单向链表⾸先，我们设计⼀个对象Node，对象⾥⾯只含有两个字段，分别是data域和next域并添加上getter、setter⽅法，这个代码很简单class Node{private String data;private Node next;public Node(String data, Node next){ = data; = next;}public String getData(){return data;}public void setData(String data){ = data;}public Node getNext(){return next;}public void setNext(Node next){ = next;}@Overridepublic String toString(){return "Node{" +"data='" + data + ''' +'}';}}接下来，就是设计API了，⼀个链表应该拥有插⼊、删除、打印、获取链表长度等功能。⾸先，我们来讨论⼀下主要的API的功能：插⼊：我们要实现的功能是，在i元素之前插⼊某个新节点。如图：本来第 i 个节点是直接指向第 i+1 个节点的，由于来了新节点，我们就需要更改⼀下指向的顺序。我们要做的具体步骤有三个：① 找到第i个元素的节点② 将该节点的next域指向我们传⼊的新节点③ 将新节点的next域指向第 i+1 个节点很简单，是不是？不过，仔细⼀看上⾯这三个步骤，事情并没有那么简单。我们想⼀想，如果实现了步骤②，那么到了步骤③，我们如何去表⽰ i 元素的 next 域呢？ 当前状态下， i 元素的 next 域可是新节点噢(步骤②做的事情)。所以我们丢失了原先 i 节点的下⼀节点，怎么办呢换个⾓度想⼀下，先实现步骤③就可以了。我们先将新节点指向第 i+1个节点，然后再把 i 节点指向新节点，就可以了(链表当中，顺序很重要)。删除⽽删除的思路跟插⼊是差不多的，实现的效果是：传⼊第i个位置的上⼀个位置，然后删除它下⼀个节点，再连向下⼀节点的下⼀节点。为什么不直接找到节点然后直接删除呢？因为该链表是单向的，没办法表⽰“当前节点的上⼀个节点”，所以我们⽆法让“上⼀个节点”与“下⼀个节点相连”。所以思路是：从链表头节点⼀直往下找，找i -1次，就找到了所删除节点的上⼀节点。好了，说完思路，我把完整代码贴出来：class singleLinkedList{/*** 传⼊⼀个头结点，遍历链表*/public void list(Node head){Node temp = t(); // 头结点的下⼀节点while (true) {if (temp == null) {// 找到最后节点,跳出循环break;}n(temp);temp = t();}}/*** 传⼊参数i，删除第i个元素*/public Node delete(Node head, int i){Node temp = t(); // 辅助节点, 指向了头结点的下⼀节点for (int j = 1; j < i; j++) {if (temp != null){temp = t(); // 辅助节点往后移动}else{ // 说明t() == null ，已经到了尾结点n("链表长度不⾜"+i+",请重新传参");return null;}}// 跳出循环，表⽰找到要删除节点的上⼀节点Node two_next = t().getNext(); // 找到下⼀节点的下⼀节点，记为two_t().setNext(null); // 将下⼀节点的值设置为空t(two_next); // 将当前节点直接指向two_nextreturn head;}/*** 传⼊参数i，在i-1的元素前⾯插⼊,node是要插⼊的节点*/public void insert(Node head, int i, Node node){Node temp = head; // 辅助节点for (int j = 1; j < i; j++) {if (temp == null) {// 下⼀节点为空，表⽰链表长度不够n("链表长度不⾜"+i+",请重新传参");break;}else{temp = t();}}// 跳出循环时，temp表⽰要插⼊节点位置的上⼀个节点Node nextNode = t();t(nextNode);t(node);}/*** 返回链表的长度* @return*/public int getLength(Node head){int count = 0;Node temp = t();while (temp != null){temp = t();count++;}return count;}}汗...这样搞得我好像⽂章很长⼀样，这样会不会拉到这⾥的⼈变少了很多？？不过当年写爬⾍⽂章的时候，这么长的⽂是常有的事，哈哈。然后，觉得写的还可以的，点个赞让我知道你来过好吗(卑微)环形链表将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成⼀个环,这种头尾相接的单链表称为单循环链表,简称循环链表(circular linked list)。循环链表如图所⽰：跟链表结构没有多⼤差别，只不过我们判断是否是尾结点的⽅式由 == null 改成了 == head(头结点)当next域指向的是头结点时，我们认为当前节点为尾结点。环形链表的好处：当我们总是要获取最后⼀个节点时，可以使⽤环形链表。⾸先实例化⼀个指向尾结点的变量，这意味着遍历时总是从尾结点开始找，对于前⼏个元素，只不过把操作数+1；⽽原本我们想要获取最后⼀个元素需要操作n次(链表节点个数的⼤⼩)，⽽现在，有了环形链表，访问最后⼀个节点的操作数是1。但是我们发现，这还是有些不够灵活，如果我们想要获取倒数第⼆个节点怎么办？这时候，双向链表就起到了作⽤……双向链表双向链表，就是可以通过两个⽅向遍历链表，别看这图画的有些复杂，其实就是多了⼀个pre域(与next域相对的)，⽤于指向上⼀个节点。双向链表的优点：双向链表相对于单链表来说,要更复杂⼀些,不过,双向链表使得对某个结点的前后结点的操作,带来了⽅便,可以有效提⾼算法的时间性能。说⽩了,就是⽤空间来换时间。对于双向链表的操作，也就是多了⼏步，但原理是⼀样的。下⾯举个添加节点的例⼦表明⼀下：步骤①：将node(新节点)的pre域指向temp步骤②：新节点指向下⼀节点步骤③：下⼀节点的上⼀节点指向新节点步骤④：当前节点的下⼀节点指向node嗯…好啰嗦好啰嗦，简单来说，就是多了⼀个pre域，但是指向域的操作顺序是很重要的，不然就发⽣丢失节点的情况了(参考单向链表)。添加代码实现：假设，现在有个新节点node，temp为想要添加位置的前⼀个位置节点。嗯，为了⽂章篇幅，这⾥贴出的是伪代码，你们看懂了就好啦~if ( != null){ // 如果这个节点不是尾结点temp = ; // 当前节点下⼀节点指向node(新节点) = ; // 新节点指向下⼀节点 = node; // 下⼀节点的上⼀节点指向新节点 = temp; // 当前节点的下⼀节点指向node}else{ // 如果这个节点是尾结点 = node; = temp;}写在后⾯这个系列会⼀直写，后⾯的还有数组、队列、还有我还没学的⼆叉树等等。对于知识点梳理的同时，⼜创作了⼀篇博客，还有各位⼩伙伴点的赞，这给我带来⽆穷⼤的动⼒。冲冲冲！！