网盘做扩大网站服务器,接网站建设_网站设计,学习做网站的,合肥网站建设哪个公司做得比较好数据结构与算法–链表实现以及应用
链表是面试时候使用最频繁的一种数据结构。链表的结构简单#xff0c;他由指针将若干个节点链接成链状结构。链表的创建#xff0c;插入#xff0c;删除#xff0c;查询操作都只有几行代码可以完成#xff0c;代码量比较少#xff0c;…数据结构与算法–链表实现以及应用
链表是面试时候使用最频繁的一种数据结构。链表的结构简单他由指针将若干个节点链接成链状结构。链表的创建插入删除查询操作都只有几行代码可以完成代码量比较少可以在较短的时间内完成这样可以在短时间内考察出人员对数据结构的理解。而且链表数据结构很灵活可以用来各种灵活的试题。链表是一种动态数据结构因为在建立链表的时候无需知道链表的长度当插入一个节点时候只需要为新节点分配内存然后调整链表中对应节点的指针指向就可以完成节点的插入。内存分配不是在创建链表的时候一次性完成而是每添加一个节点分配一个节点的内存由于没有和数组一样的闲置的内存所以链表比之数组的内存利用率更高。我们用如下方式定义链表节点
/*** 链表元素节点** author liaojiamin* Date:Created in 12:17 2021/3/5*/
public class ListNode implements ComparableListNode {private String key;private Integer value;private ListNode next;private ListNode before;public ListNode() {}public ListNode(String key, Integer value){this.key key;this.value value;this.next null;this.before null;}public ListNode(Integer value) {this.value value;this.next null;this.before null;}public String getKey() {return key;}public void setKey(String key) {this.key key;}public Integer getValue() {return value;}public void setValue(Integer value) {this.value value;}public ListNode getNext() {return next;}public void setNext(ListNode next) {this.next next;}public ListNode getBefore() {return before;}public void setBefore(ListNode before) {this.before before;}Overridepublic int compareTo(ListNode o) {return this.value - o.value;}
}
话不多说我们如下实现单向链表的CURD
/*** 单向链表实现** author liaojiamin* Date:Created in 12:21 2021/3/5*/
public class MyLinkedList {/*** 链表尾部添加节点*/public static ListNode addToTail(ListNode head, String key, Integer value) {ListNode newNode new ListNode(key, value);if (head null) {head newNode;}else {ListNode pointNode head;while (pointNode.getNext() ! null){pointNode pointNode.getNext();}pointNode.setNext(newNode);}return head;}/*** 链表尾部添加节点*/public static ListNode addToTail(ListNode head, ListNode newNode) {if (head null) {head newNode;}else {ListNode pointNode head;while (pointNode.getNext() ! null){pointNode pointNode.getNext();}pointNode.setNext(newNode);}return head;}/*** 从头打印链表数据* */public static void print(ListNode head){if(head null){System.out.println(is empty list);}ListNode pointNode head;while (pointNode ! null){System.out.print(pointNode.getValue());System.out.print(, );pointNode pointNode.getNext();}}/*** 查找节点* */public static ListNode search(ListNode head, Integer value){if(head null || value null){System.out.println(not in);}ListNode pointNode head;while (pointNode ! null){if(pointNode.getValue() value){System.out.println(is in);return pointNode;}else {pointNode pointNode.getNext();}}System.out.println(not in);return null;}/*** 通过key查找节点* */public static ListNode search(ListNode head, String key){if(head null || key null){System.out.println(not in);}ListNode pointNode head;while (pointNode ! null){if(pointNode.getKey().equals(key)){System.out.println(is in);return pointNode;}else {pointNode pointNode.getNext();}}System.out.println(not in);return null;}/*** 删除节点* */public static ListNode delete(ListNode head, Integer value){if(head null || value null || head.getNext() null){return head;}ListNode delNode null;if(head.getValue() value){head head.getNext();delNode head;}else {ListNode pointNode head;while (pointNode.getNext() ! null pointNode.getNext().getValue() ! value){pointNode pointNode.getNext();}if(pointNode.getNext() ! null pointNode.getNext().getValue() value){delNode pointNode.getNext();pointNode.setNext(pointNode.getNext().getNext());}}if(delNode ! null){System.out.println(delete success val delNode.getValue());}return head;}public static void main(String[] args) {Random random new Random(100);ListNode myHead new ListNode(random.nextInt(100));for (int i 0; i 20; i) {addToTail(myHead, random.nextInt(100));}print(myHead);if(search(myHead, 74)){delete(myHead, 74);}print(myHead);System.out.println();// printOver(myHead);System.out.println();// printOver_2(myHead);}
}由于链表内存不是一次性分配所以内存是不连续的通过指针来关键每个节点的内存地址因此我们也不能像数组一样通过下标去获取对应的节点只能从头开始遍历节点找到第 i 个节点时间复杂度是O(n)。
变种题型
简单的单向链表实现的基础上我们看一个特别的从尾到头打印单向链表中每个节点值
分析
单向链表从尾开始打印简单的做法是将链表中的指针反转但是这样会改变元数据的结构但是打印一般是只读的这样显然不可行顺序打印可以直接从头结点开始读取就可以要从尾到头反转也就是说有如下特性第一个先遍历但是他必须最后输出此时我们可以借助其他的数据结构将第一次遍历看出输入也就是第一个输入的必须最后一个输出这是典型的先进后出的顺序栈很显然符合这种标准我们有如下实现 /*** 栈方法* 从尾到头打印单向链表值* */public static void printOver(ListNode head){MyStack myStack new MyStack();if(head null){return;}ListNode pointNode head;while (pointNode ! null){myStack.push(pointNode.getValue().toString());pointNode pointNode.getNext();}while (!myStack.isEmpty()){System.out.print(myStack.pop());System.out.print(, );}}注意此处用的myStack用的上一节中自己实现的栈详情点击以上实现用栈可以实现那么一定可以用递归来完成因为递归本质上就是栈的一种结构那么我们用递归每次打印节点的时候都判断是否有子节点有则下打印子节点如下实现。
/*** 递归方式* 从尾到头打印单向链表* */public static void printOver_2(ListNode head){if(head null){return;}ListNode pointNode head;if(pointNode.getNext() ! null){printOver_2(pointNode.getNext());}System.out.print(pointNode.getValue());System.out.print(, );}问题以上递归方式的代名词看起来更简单一点但是有一个问题当链表长度非常长的时候可能会导致函数栈溢出。而之前用栈的方法虽然需要两次循环但是代码的鲁棒性还是要更好一点因此我认为最优解是使用栈的方式。
上一篇数据结构与算法–利用栈实现队列 下一篇数据结构与算法–查找与排序另类用法
