【实现简易的LinkedList】模拟Java中的双向链表

**前言：**LinkedList底层是使用双向链表实现的，我们就来实现一个简易的MyLinkedList吧

分析：首先实现一个Node类用来存放所需存储的内容和上一个元素的地止和下一个元素的地址，再实现一个MyLinkedList类在里面定义Node属性first和last用来表示首尾节点，定义一个计数器用来表示添加次数，然后来实现add、size、get方法，具体实现过程请看0x001

由分析得，我们得创建一个Node类，可以封装三个属性，用来上一个节点地址、下一个节点地址和所需存储的内容，并实现toString方法

public class Node {
	//三个属性
	//上一个节点的地址
	private Node pre;
	//当前存入的元素
	private Object obj;
	//下一个节点的地址
	private Node next;
	public Node getPre() {
		return pre;
	}
    //封装节点的属性
	public void setPre(Node pre) {
		this.pre = pre;
	}
	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;
	}
	@Override
	public String toString() {
		return "Node [pre=" + pre + ", obj=" + obj + ", next=" + next + "]";
	}
}

我们实现了Node类后，就来实现MyLinkedList类吧。

1. 定义属性和构造方法

public class MyLinkedList{
    //首尾元素
    Node first;
    Node last;
    //计时器
    int count=0;
    public MyLinkedList(){}
}

2. 实现add方法：添加元素

public class MyLinkedList{
    //add方法添加元素
    public void add(Object obj){
        //如果first等于null，说明第一次添加元素
        if(first==null){
            //创建一个节点对象，并存入传入的元素
            Node n=new Node();
            //由于第一次添加，节点中的上一个节点使用null
            n.setPre(null);
            //在节点中存入元素
            n.setObj(obj);
            //由于第一次添加，节点中的下一个节点使用null
            n.setNext(null);
            //由于第一次添加，所以首尾节点（first和last）等于obj
            first=n;
            last=n;
        }else{
            //first不等于null，说明不是第一次添加元素，每次添加元素都一样了
            //创建节点对象
            Node n=new Node();
            //在节点中的上一个节点存入last
            n.setPre(last);
            //在节点中存入元素
            n.setObj(Obj);
            //在节点中的下一个节点存入null
            n.setNext(null);
            //在last中设置下一个节点为n
            last.setNext(n);
            //将n赋值给last
            last=n;
        }
        //添加元素的次数
        count++
    }
}

3.size方法：获取元素个数

public class MyLinkedList{
    public int size(){
        return count;
    }
}

4.get方法：下标从零开始获取元素数据

public class MyLinkedList{
    //下标从零开始获取元素数据
    public Object get(int index){
        Node n=first;
        //寻找下标为index的节点
        for(int i=0;i
            n=n.getNext();
        }
        return n.getObj();
    }
}

5.整理得：add方法、size方法、get方法构成简易的MyLinkedList类

public class MyLinkedList{
    //首尾元素
    Node first;
    Node last;
    //计时器
    int count=0;
    public MyLinkedList(){}
    //add方法添加元素
    public void add(Object obj){
        //如果first等于null，说明第一次添加元素
        if(first==null){
            //创建一个节点对象，并存入传入的元素
            Node n=new Node();
            //由于第一次添加，节点中的上一个节点使用null
            n.setPre(null);
            //在节点中存入元素
            n.setObj(obj);
            //由于第一次添加，节点中的下一个节点使用null
            n.setNext(null);
            //由于第一次添加，所以首尾节点（first和last）等于obj
            first=n;
            last=n;
        }else{
            //first不等于null，说明不是第一次添加元素，每次添加元素都一样了
            //创建节点对象
            Node n=new Node();
            //在节点中的上一个节点存入last
            n.setPre(last);
            //在节点中存入元素
            n.setObj(Obj);
            //在节点中的下一个节点存入null
            n.setNext(null);
            //在last中设置下一个节点为n
            last.setNext(n);
            //将n赋值给last
            last=n;
        }
        //添加元素的次数
        count++;
    }
    public int size(){
        return count;
    }
     //下标从零开始获取元素数据
    public Object get(int index){
        Node n=first;
        //寻找下标为index的节点
        for(int i=0;i
            n=n.getNext();
        }
        return n.getObj();
    }
}

public class Test{
	public static void main(String[] args) {
        //创建MyLinkedList对象
		MyLinkedList mll=new MyLinkedList();
        //添加元素
		mll.add("你好");
		mll.add("3Q");
		mll.add("zhoukali");
        //获取下标为2的元素
		System.out.println(mll.get(2));
        System.out.println("-----------------");
        //遍历MyLinkedList集合
		for(int i=0;i
			System.out.println(mll.get(i));
		}
	}
}

运行效果：

实现泛型版的MyLinkedList

**原因：**上面那种版本有一个明显的缺陷，数据类型不安全，不能固定一个相同的数据，为了约束数据类型我们可以实现一个泛型版的MyLinkedList

**改进：**我们把Node接口放在LinkedList类中，实现内部类方便管理

上代码：MyLinkedList类

public class MyLinkedList{
	class Node {
		//三个属性
		//上一个元素的地址
		private Node pre;
		//当前存入的元素
		private E obj;
		//下一个元素的地址
		private Node next;
		public Node getPre() {
			return pre;
		}
		 //封装节点的属性
		public void setPre(Node pre) {
			this.pre = pre;
		}
		public E getObj() {
			return obj;
		}
		public void setObj(E obj) {
			this.obj = obj;
		}
		public Node getNext() {
			return next;
		}
		public void setNext(Node next) {
			this.next = next;
		}
		@Override
		public String toString() {
			return "Node [pre=" + pre + ", obj=" + obj + ", next=" + next + "]";
		}
	}
    //首尾元素
    Node first;
    Node last;
    //计时器
    int count=0;
    public MyLinkedList(){}
    //add方法添加元素
    public void add(E obj){
        //如果first等于null，说明第一次添加元素
        if(first==null){
            //创建一个节点对象，并存入传入的元素
            Node n=new Node();
            //由于第一次添加，节点中的上一个节点使用null
            n.setPre(null);
            //在节点中存入元素
            n.setObj(obj);
            //由于第一次添加，节点中的下一个节点使用null
            n.setNext(null);
            //由于第一次添加，所以首尾节点（first和last）等于obj
            first=n;
            last=n;
        }else{
            //first不等于null，说明不是第一次添加元素，每次添加元素都一样了
            //创建节点对象
            Node n=new Node();
            //在节点中的上一个节点存入last
            n.setPre(last);
            //在节点中存入元素
            n.setObj(obj);
            //在节点中的下一个节点存入null
            n.setNext(null);
            //在last中设置下一个节点为n
            last.setNext(n);
            //将n赋值给last
            last=n;
        }
        //添加元素的次数
        count++;
    }
    public int size(){
        return count;
    }
     //下标从零开始获取元素数据
    public E get(int index){
        Node n=first;
        //寻找下标为index的节点
        for(int i=0;i
            n=n.getNext();
        }
        return n.getObj();
    }
}

**测试一下：**Test类和运行结果

class Test{
	public static void main(String[] args) {
		MyLinkedList mll=new MyLinkedList();
		mll.add("你好");
		mll.add("3Q");
		mll.add("zhoukali");
		System.out.println(mll.get(2));
		System.out.println("-----------------");
		for(int i=0;i
			System.out.println(mll.get(i));
		}
	}
}