自我理解java linkedlist插入数据的算法:
首先看一下,linkedlist插入源代码:
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
private transient Entry header = new Entry(null, null, null);//初始化时先实例一个header,链表头
/**
* Constructs an empty list.//构造一个空链表
*/
public LinkedList() {
header.next = header.previous = header; //把链表头和尾先连到自己(1)
addBefore(e, header);(2)
}
.......
public boolean add(E e) {//插入链表方法
return true;
}
.......
private static class Entry {//每个数据存放,所要用到的静态内部类
E element;
Entry next;//后一个节点
Entry previous;//接一个节点
Entry(E element, Entry next, Entry previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
//插入操作方法
private Entry addBefore(E e, Entry entry) {
Entry newEntry = new Entry(e, entry, entry.previous);(3)
newEntry.previous.next = newEntry;(4)
newEntry.next.previous = newEntry;(5)
size++;(6)
modCount++;
return newEntry;
}
/*其他方法~~*/
以上部分就是算法所在:(一个简单的公式替换过程)
算法步骤(对应上面的编号):
(1)实例化一个header (Entry)
header.next = header
header.previous = header
当有第一条数据插入链表:
(3)实例化一个 Entry newEntry (以下简称E1)
E1.next = header
E1.previous = header.previous
E1.previous.next = header.previous.next = header.next
(4)由上面可得:
newEntry.previous.next = newEntry;
作用:
相当于 E1.previous.next = header.next = E1
其实就是,让上一个节的next指向下一个节点数据
所以header.next 的下一个节点就是E1
(5)E1.next.previous = header.previous = E1(这里用得巧妙)
其实这个用法单从E1.next.previous= E1单这么看,很直观因为E1的下一个节点数据的上一个节点就应该是E1
从上面可知,E1.next == header,为什么要把header.previous = E1呢?
其实包含着一个递归在里面。
如果再新增一个数据 Entry E2 :
从上面的代码可以看出,E2的实例化过程是:(其实linkedlist每次新增一个数据,都通过header传值)
Entry E2 = new Entry(data, header, header.previous);
主意代码部分的负值。关键就是这里,实例化的时候,E2.previous = header.previous = E1
简单得完成了负值过程。
然后 E2.previous.next = E1.next = E2
E2.next.previous = header.previous = E2 .......(接着插入下一条数据,如此递归)
(6)记录链表位数
设计到了一个小小的递归算法。
linkedlist记录一。完毕。。
分享到:
相关推荐
│ Java面试题10.ArrayList LinkedList.mp4 │ Java面试题11.HashMap和HashTable的区别.mp4 │ Java面试题12.实现一个拷贝文件的类使用字节流还是字符串.mp4 │ Java面试题13.线程的实现方式 怎么启动线程怎么区分...
入坑笔记,劝退一波,别搞后端了,转算法去吧! Java 设计模式 算法 网络 操作系统 数据库 Spring 分布式 大数据 目录 Java 1. 基础 基础:数据与程序结构、关键字等。 对象与类:继承、接口、抽象类、内部类、枚举...
学习笔记(持续更新中) 所有文章均同步发布到微信公众号【JavaRobot】,关注微信公众号,及时得到文章推送,谢谢支持。 说明:如无特别说明,所有代码都基于JDK8 JavaSE(Java基础) Java Core 关键字 synchronized...
{4.2}\ttfamily java.util.LinkedList}{81}{section.4.2} {4.3}贪吃蛇案例}{82}{section.4.3} {4.4}散列表与HashMap}{83}{section.4.4} {4.4.1}java.util.HashMap}{83}{subsection.4.4.1} {4.5}\ttfamily java....
一、数据结构与算法 数据结构与算法 排序算法、动态规划、递归、回溯法、贪心算法等。 二、Java Java 基础概念 基本概念、面相对象、关键字、基本数据类型与运算、字符串与数组、异常处理、Object通用方法 Java ...
编程笔记 学习、总结、记录 ! —— since 2018/20 :bar_chart: :hot_beverage: :mobile_phone: :laptop: :floppy_disk: :pager: :globe_with_meridians: :file_cabinet: :books: :bar_chart: 算法和数据结构 排序...
此为学习算法之笔记&算法代码实现过程 使用Python代码完全实现 Algorithm File Data_Structure 数据结构的相关实现方法 Algorithm_idea 常见的算法思想实现方法 Search_Alg 查找算法 Sort_Alg 排序算法 Recursion_...
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)...
java中的数据结构笔记 api java中常用的api problem 真正的题 array 数组 binary 二分查找 backtracking 回溯算法 bit 位运算 bs 二分查找 binary search doublePointer 双指针 dp 动态规划 dynamic program greedy ...
1、Java 相关 容器(HashMap、HashSet、LinkedList、ArrayList、数组等) 需要了解其实现原理,还要灵活运用,如:自己实现 LinkedList、两个栈实现一个队列,数组实现栈,队列实现栈等。 内存模型 垃圾回收算法...
课程作业本课程旨在帮助您深入了解数据结构和算法。...笔记每次练习最多可能需要1个小时。 总持续时间估计为30小时。 这些解决方案是用Java编写的,但是如果您决定进行面试,则可以使用偏好的语言。
java lru leetcode 力码 我在 Leetcode 上的练习为我已解决的每个问题创建一个索引。 笔记 问问题 示例(数据类型、最大值、溢出) 边缘情况 算法(时间复杂度,空间复杂度) 代码 通过示例和边缘情况 优化(权衡,...