源代码：https://gitee.com/AgentXiao/Collection
一、LinkedList底层实现
LinkedList的底层是双向链表。该链表由多个节点组成。
package pri.xiaowd.demo02;
/**
* @ClassName Node
* @Description 节点
* @Author xwd
* @Date 2018/10/7 11:07
*/
public class Node {
private Node previous;//上一个节点
private Object obj;//存储的对象
private Node next;//下一个节点
public Node() {
}
public Node(Node previous, Object obj, Node next) {
this.previous = previous;
this.obj = obj;
this.next = next;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
2、自己实现一个LinkedList
（1）在链表中，比较重要的是第一个节点和最后一个节点。
private Node first;//第一个节点
private Node last;//最后一个节点
（2）add(Object obj)方法
add(Object obj)
/**
* @MethodName add
* @Descrition 添加一个节点
* @Param [object]
* @return void
*/
public void add(Object object){
Node node = new Node();
//如果第一个链表都是空的，说明添加的是第一个节点
if(first == null){
node.setPrevious(null); //第一个节点的上一个节点是null
node.setObj(object); //第一个节点的内容
node.setNext(null); //第一个节点的下一个节点也暂时是空的
first = node; //添加了第一个节点之后第一个和最后一个都是新添加的
last = node;
}else{ //直接在最后一个节点的后面添加
node.setPrevious(last); //新添加的节点的上一个节点是之前的最后一个
node.setObj(object); //新添对象
node.setNext(null); //新添加的节点的下一个节点是null
last.setNext(node); //形成链表，原先的最后一个的下一个节点设置为新增的节点
last = node; //将最后一个节点设置为新增的节点
}
size++; //长度+1
}
（3）我们来测试一下
public static void main(String[] args) {
MyLinkedList mll = new MyLinkedList();
mll.add("aaa");
mll.add("bbb");
System.out.println(mll.size);
}
得到如果示意图：
debug示意图
（4）get(int index)：因为链表是没有下标的，所以只能从头开始一个一个遍历。
首先需要进行索引值越界判断
/**
* @MethodName rangeCheck
* @Descrition 索引检测
* @Param [index]
* @return void
*/
private void rangeCheck(int index){
if(index < 0 || index >= size){
throw new RuntimeException("你输入的索引值不在范围之内！");
}
}
获取一个对象，特别需要注意循环遍历的时候什么时候就能得到想要的对象
/**
* @MethodName getNode
* @Descrition 找到指定位置的节点
* @Param [index]
* @return pri.xiaowd.demo02.Node
*/
public Node getNode(int index){
Node temp = null;
if(first != null){
temp = first;
for(int i=0;i<index;i++){
temp = temp.getNext();
}
}
return temp;
}
/**
* @MethodName get
* @Descrition 获取指定位置节点的内容
* @Param [index]
* @return java.lang.Object
*/
public Object get(int index){
rangeCheck(index);
Node temp = getNode(index);
return temp.getObj();
}
（5）移除指定位置的节点remove(int index)
remove.png
/**
* @MethodName remove
* @Descrition 移除指定索引位置的节点
* @Param [index]
* @return void
*/
public void remove(int index){
rangeCheck(index);
//找到索引位置的节点
Node temp = getNode(index);
if(temp != null){
Node upNode = temp.getPrevious();
Node downNode = temp.getNext();
upNode.setNext(downNode);
downNode.setPrevious(upNode);
size -- ;
}
}
（6）add(int index,Object obj)
add(int index,Object obj)
index=1的情况
/**
* @MethodName add
* @Descrition 在指定位置插入对象
* @Param [index, obj]
* @return void
*/
public void add(int index,Object obj){
rangeCheck(index);
Node temp = getNode(index);//得到索引位置的节点
Node newNode = new Node();//创建新的节点
newNode.setObj(obj);
if(index == 0){ //如果想在第一个位置插入，不考虑索引位置的节点是否为空
newNode.setPrevious(null);
newNode.setNext(temp);
temp.setPrevious(newNode);
first = newNode;
}else{
if(temp != null) { //实际上经过了索引检测之后，temp不会为空
Node upNode = temp.getPrevious();//得到上一个节点
upNode.setNext(newNode);
newNode.setPrevious(upNode);
newNode.setNext(temp);
temp.setPrevious(newNode);
}
}
size++;
}
（7）set(int index,Object obj)
set(int index,Object obj)
/**
* @MethodName set
* @Descrition 在指定的索引位置替换对象
* @Param [index, obj]
* @return void
*/
public void set(int index,Object obj){
rangeCheck(index);
Node temp = getNode(index);//得到索引位置的节点
Node newNode = new Node();//创建新的节点
newNode.setObj(obj);
if(index == 0){
newNode.setPrevious(null);
newNode.setNext(temp.getNext());
temp.getNext().setPrevious(newNode);
first = newNode;
}else if(index == size-1){
newNode.setNext(null);
newNode.setPrevious(temp.getPrevious());
temp.getPrevious().setNext(newNode);
last = newNode;
}else{
Node upNode = temp.getPrevious();
Node downNode = temp.getNext();
upNode.setNext(newNode);
newNode.setPrevious(upNode);
newNode.setNext(downNode);
downNode.setPrevious(newNode);
}
}
(8)remove(Object obj)
remove(Object obj)
/**
* @MethodName getNode
* @Descrition 根据obj查找对应的节点
* @Param [obj]
* @return pri.xiaowd.demo02.Node
*/
public Node getNode(Object obj){
Node temp = first;
if(first != null){
for(int i=0;i<size;i++){
if(temp.getObj().equals(obj)){
return temp;
}
temp = temp.getNext();
}
}
return temp;
}
/**
* @MethodName remove
* @Descrition 移除指定的节点
* @Param [obj]
* @return void
*/
public void remove(Object obj){
Node node = getNode(obj);
Node downNode = node.getNext();
Node upNode = node.getPrevious();
if(node.getPrevious() == null){ //如果是第一个节点
downNode = node.getNext();
downNode.setPrevious(null);
first = downNode;
}else if(node.getNext() == null){ //如果是最后一个节点
upNode = node.getPrevious();
upNode.setNext(null);
last = upNode;
}else{ //如果是中间的节点
upNode.setNext(downNode);
downNode.setPrevious(upNode);
}
size--;
}
三、总结
最为重要的，是能够画出链表的图示，对着图示进行代码的编写。
【补充】细节完善
对于get(int index)方法，如果始终从0开始遍历话，当index较大时，效率太低。因此可以使用二分法进行拆分，提高效率。
/**
* @MethodName getNode
* @Descrition 找到指定位置的节点
* @Param [index]
* @return pri.xiaowd.demo02.Node
*/
public Node getNode(int index){
Node temp = null;
if(first != null){
if(index < (size >> 1)){
temp = first;
for(int i=0;i<index;i++){
temp = temp.getNext();
}
}else{
temp = last;
for(int i=size-1;i>index;i--){
temp = temp.getPrevious();
}
}
}
return temp;
}
网友评论