手写LinKedList双向链表_c++ 手写双向链表

链表结构图

   a1,a2..都代表每个Node节点。

1：新建一个自定义的节点

package com.kiven.linKedList;
 
 
public class Node<E> {
    public   E item; //存放数据的泛型
    public   Node<E> prev; //上一个节点 这里这个Node 指向自己本身
    public   Node<E> next; //下一个节点 这里这个Node 也指向自己本身  
    
    public Node() {
          super();
    }
 
 
    //有参构造
       Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
    
             
}
2：新建一个自定义的LinKedList，里面只有三个基本对象，这里一定要有一个思想的转变，这里存对象不像数组，这里是从first这个对象开始往下存，first节点对象的next又存入一个节点对象，以此类推。

MyLinKedList<E> 

       public int size = 0;//容量
 
     public Node<E> first;//第一个节点
 
     public Node<E> last;//最后一个节点
3：最基本的方式进行实现。

//实例化我们的myLinKedList  
        MyLinKedList<String> myLinKedList = new MyLinKedList<>();
        
        //假如我们要把这三个对象放入myLinKedList
        String s1="a";
        String s2="b";
        String s3="c";
        
        //第一次 把s1放入
        
        Node<String> node =new Node<String>(null,s1,null);//第一次存入作为第一个节点，该节点没有上一个 所以第一个参数 null
        myLinKedList.first=node;//第一次存入作为第一个节点
        myLinKedList.last=node;//第一次存入也作为最后一个节点
        myLinKedList.size=1;//容量变为1
        
        
        Node<String> node2 =new Node<String>(node,s2,null);//第二次存入 ，第一个的node节点就作为第二次的上一个节点。
        node.next=node2;//第一个节点的下一个节点
        myLinKedList.last=node2;//最后一个节点
        myLinKedList.size=2;
        
        
        Node<String> node3 =new Node<String>(node2,s3,null);//一次类推。
        node2.next=node3;
        myLinKedList.last=node3;
        myLinKedList.size=3;
main方法运行 结构图如下：

此时链表的结构就已经出来了，就是一个节点接一个节点。

first a节点下的next对象包含了一个节点b，b节点的next对象包含了一个节点c,以此类推的结构。

写一个get方法：

   //get方法 很简单 根据游标 从第一个节点遍历寻找值 这里也可以很清楚的看到为什么链表查询慢  不像arrayList那样查询快 
    //因为这里是遍历  arrayList是直接根据下标从数组取值，所以arrayList查询要快的多。 
    public E get(int index) {
        return node(index).item;
    }
    
    
    //这里是源码直接复制过来的 
    //很巧妙的设计  如果我们查询的这个值排在队伍的后半部分， 从后往前找  。小于后半部分 从前往后找  可以提高效率
    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
最后贴上jdk 原版add 方法：

//这里是jdk里的源码
    void add(E e) {
        final Node<E> l = last;//把最后一个赋予新的对象，第一次是空的
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;//每一次新加入的节点都是最后一个节点
        if (l == null) //第一次l是空的
            first = newNode;//第一个节点就是新加入的节点
        else
            l.next = newNode;//否则l的下一个是新加入的节点  这里有点绕，需要一点点调式，是对象的引用改变了first的指定对象
        size++;
    }

/**
 * 每个节点内三个对象表示
 * previous 前一个节点位置
 * obj 当前节点数据信息
 * next 下一个节点位置
 * @author Administrator
 *
 */
public class Node {
 
     Node previous;
     Object obj;
     Node next;
    
    public Node(){
        
    }
    
    public Node(Node previous,Object obj,Node next){
        super();
        this.previous = previous;
        this.obj = obj;
        this.next = next;
    }
 
    public Object 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 Object getNext() {
        return next;
    }
 
    public void setNext(Node next) {
        this.next = next;
    }
    
}

/**
 * 编程实现LinkedList
 * 
 * @author Administrator
 *
 */
public class MyLinkedList {
 
    private Node first;
    private Node last;
    private int size;
 
    public MyLinkedList() {
 
    }
 
    public int size() {
        return size;
    }
 
    // 在链表尾部增加指定对象
    public void add(Object obj) {
        Node n = new Node();
        // 链表头是否为空
        if (first == null) {
 
            n.setPrevious(null);
            n.setObj(obj);
            n.setNext(null);
            first = n;
            last = n;
 
        } else {
            // 向last节点后增加新的节点
            n.setPrevious(last);
            n.setObj(obj);
            n.setNext(null);
 
            last.setNext(n);
 
            last = n;
 
        }
        size++;
    }
 
    // 向指定索引位置增加对象，新节点的对应关系为:previous指向索引位置节点的前一个节点,next指向索引位置节点
    public void add(int index, Object obj) {
        rangeCheck(index);
        Node temp = node(index);
 
        Node up = temp.previous;
        Node newNode = new Node();
        newNode.obj = obj;
 
        if (temp != null) {
 
            newNode.previous = up;
            up.next = newNode;
 
            newNode.next = temp;
            temp.previous = newNode;
            size++;
        }
 
    }
 
    public void set(int index, Object obj) {
        rangeCheck(index);
        Node temp = node(index);
 
        if (temp != null) {
            temp.obj = obj;
        }
    }
 
    public Object get(int index) {
        rangeCheck(index);
        Node temp = node(index);
        if (temp != null) {
            return temp.obj;
        } else {
            return null;
        }
 
    }
 
    // 移除索引位置节点,1 2 3,将1的下一个设置为3,3的上一个设置为1,实现双向,移除2位置
    public void remove(int index) {
        Node temp = node(index);
        if (temp != null) {
            // 索引位置节点的上一个节点
            Node up = temp.previous;
            // 索引位置节点的下一个节点
            Node down = temp.next;
            // 上一个节点的next节点位置设置为当前节点的下一个,同理操作下一个节点,实现移除索引位置节点
            up.next = down;
            down.previous = up;
        }
        size--;
    }
 
    public void clear() {
        Node temp = new Node();
        if (first != null) {
            temp = first;
            for (int i = 0; i < size - 1; i++) {
                temp.obj = null;
                temp = temp.next;
                size--;
 
            }
 
        }
 
    }
 
    public void rangeCheck(int index) {
        if (index < 0 || index > size - 1) {
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }
 
    // 寻找节点
    public Node node(int index) {
        rangeCheck(index);
        Node temp = null;
        
        if (first != null) {
            
            //size=50;[0,49],寻找第2个和寻找第48个节点的方法优化分析
            //一个简单的优化算法:将index与size/2(szie>>1)进行比较,如果小于则从0开始遍历,如果大于则从49开始向前遍历
            if (index<(size>>1)) {
                temp = first;
                for (int i = 0; i < index; i++) {
                    temp = temp.next;
                }
            }else{
                temp = last;
                for (int i = size-1; i > index; i--) {
                    temp = temp.previous;
                }
            }
            
        }
        return temp;
    }
 
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add("aaa");
        list.add(111);
        list.add(555);
        list.add(1, "ddd");
        list.set(1, 444);
        
        
        System.out.println(list.get(1));
//        for (int i = 0; i < list.size(); i++) {
//            System.out.println(list.get(i));
//        }
 
    }
 
}