java
jdk1.8,IntelliJ IDEA
首先,找到LinkedList的存储数据的地方。通过参数,我们可以发现一个Node
我们已经知道LinkedList是基于双向链表来实现的,那么它一定有一个基本的存储单元,通过上面的Node初始化,我们可以用以下图形模拟LinkedList的进本存储单元。初始化有三个数据,指向上一个节点和指向下一个节点的引用,以及真实的存储数据。
添加元素:add(E e),按顺序进行添加。创建新节点,将上个节点的last地址作为新建节点的first地址。
图形说明add原理。第一个元素的添加,此时最后一个节点和最初节点都为null,因此第一个节点既是既是first也是last。指向该节点的引用假设为0x。
在添加第二个元素时,此时last为尾结点的引用0x,此时新建的第二个节点引用假设为0x,那么,新节点引用将赋值给l.next即第一个节点的next指针。
同理当第三个元素添加时,last的值已经变更为0x,其余按照上一步骤相同。这样,就实现了向LinkedList中添加元素。
删除元素:remove(int idex)可以看到,首先查看是否有该index,然后调用node方法,先去找到该index的node,再通过unlink方法将该node的item,pre和next指针都置空,让其等待gc回收,另外将前node的next指针指向后node的pre,将后node的pre指向前node的next。插入的程序刚好和remove相反,这里不多赘述。
这里做一个简单的流程图说明remove。
LinkedList的遍历用for循环会非常慢,一般使用foreach的迭代遍历。