java的LinkedList底层方法实现与分析

LinkedList 底层实现与分析。
Learning Notes:
一、 学习了LinkedList之后，手写了简单的四个方法（大牛勿喷）。 笔记如下
二、编程思路
1.1 节点的属性定义：前驱节点，后继节点、数据域
1.2 add()方法：有两种情况
（1）当链表一个节点都没有的时候，首先创建一个节点，然后将前驱节点和后继节点都赋值为null，这样头节点和尾节点都是同一个节点。
（2）当链表中存在节点的时候，默认采用尾插法的形式添加，还是先创建一个节点，然后将新节点的前驱节点指向老节点，后继节点赋值为null；将老节点的后继节点指向新节点。
1.3 remove()方法：同样也分两种情况
（1）当链表只存在一个节点时，将该节点的前驱节点，后继节点、数据域都赋值为null即可
（2）当链表存在多个节点时，又分删除头节点或删除尾节点。
删除头节点：将头节点的后继节点变为头节点，并赋值前驱节点为null，之前的头节点的属性都赋值为null即可
删除尾节点：将尾节点的前驱节点变为尾节点，并赋值后继节点为null，之前的尾节点的属性都赋值为null即可
1.4 get()方法：先通过索引值找到节点，然后打印即可。

Linked底层存储结构

代码如下：

测试类 public class MyLinkedListTest { public static void main(String[] args) { MyLinkedList l = new MyLinkedList (); l.addFirst("你好"); l.addLast("我爱你"); l.removeLast("我爱你"); for(int i = 0; i<l.size;i++) { System.out.print(l.get(i)); } } } 

Node类 class Node { //前驱节点 Node prev; //后继节点 Node next; //数据域 Object element; //带参构造方法 public Node(Node prev, Node next, Object element) { super(); this.prev = prev; this.next = next; this.element = element; } //无参构造方法 public Node() { super(); } } 

方法实现类（核心） class MyLinkedList{ //首节点 Node first; //  尾节点 Node last; //链表长度 int size = 0; //无参构造方法 public MyLinkedList() { super(); } //添加头方法 public void addFirst(Object object) { //将f指向first成员变量 Node f = first; // 创建一个新的节点前驱为空 后继指向f节点，数据为传入的object Node n1 = new Node(null,f,object); //让first指向新创建的n1节点 first = n1; //判断f是否为空如果为空说明只有一个节点 if(f==null) { //将last 也指向n1表示first和last为同一节点。 last = n1; }else { //如果f不为空说明n1不是唯一的节点 所以将f的前驱指向n1节点 f.prev = n1; } size++; } //删除尾方法 public void removeLast(Object object) { //将f指向last成员变量 Node f = last; //将prev指向f的前驱节点。 Node prev =f.prev; //然后将f的数据域清空 f.element="null"; //	  让last也指向prev节点 last = prev; //如果last节点为空说明清空完最后一个节点再无节点 if(last==null) { //将first也设为空 表示没有数据 first = null; }else { //如果last不为空 就将last后继节点设为空 表示last为最后一个节点 last.next =null; } size--; } //删除头方法 public void removeFirst(Object object) { //将f指向first成员变量 Node f = first; //将next指向f的后继节点 Node next =f.next; //然后将f的数据域清空 f.element="null"; //		  让first也指向next节点 first = next; //如果first为空说明清空前面节点后再无其它节点 if(first==null) { //  所以让last也设为空 last= null; }else { //如果first不为空，说明还有节点，就将他前驱设为空 first.prev =null; } size--; } //添加尾方法 public void addLast(Object object) { //将f指向last成员变量 Node f = last; // 创建一个新的节点后继为空 前驱指向f节点，数据为传入的object Node n1 = new Node(f,null,object); //让last指向新创建的n1节点 last= n1; //判断f是否为空如果为空说明只有一个节点 if(f==null) { //让first指向新创建的n1节点 first = n1; }else { //如果f不为空说明n1不是唯一的节点 所以将f的后继指向n1节点 f.next = n1; } size++; } //根据索引获取链表数据 public Object get(int index){ return node(index).element; } //二分法查找 index小于size一半从前查找，不小于一半从后查找 public Node node(int index){ if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } } 

本文地址：https://blog.csdn.net/weixin_45465765/article/details/107665594