Java双向链表基本功能实现[增删改查]

Java双向链表基本功能实现[增删改查]

• 添加节点 addIndex(int index,int val)；在双链表任意index位置添加元素val     ps:找待插入位置的前驱节点，后继节点
• 查找元素 get(int index)；根据 inedx 查找对应的元素节点值；
• 修改节点 set(int index,int newVal)；当前链表中索引为 index 的节点值改为newVal；
• 删除节点 removeIndex(int index)；删除双链表中指定索引对应的元素节点；

---

草稿图纸 ： 

 

代码 

package seqlist.doublelink;

public class DoublelinkedList {
    private int size; // 当前链表有效元素个数
    private Node head; // 头节点
    private Node tail; // 尾节点

    
    public void addFirst(int val){
        Node node = new Node(null,val,head);
        if (head==null){
            tail = node; // 当前链表为空
        }else{
            //当前链表不为空
            head.prev=node;
        }
        // 无论链表是否为空，最后node节点都是最新的头节点
        head = node;
        size++;
    }

    
    public void addLast(int val){
        Node node = new Node(tail,val,null);
        if (tail==null){
            head=node;
        }else{
            tail.next=node;
        }
        tail=node;
        size++;
    }

    
    private Node node(int index){
        Node ret = null;
        // index < size / 2(从头找)
        if (index < (size >> 1)){
            ret = head;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
        }else{
            // 此时从后向前遍历
            ret = tail;
            for (int i = size - 1; i > index; i--) {
                ret = ret.prev;
            }
        }
        return ret;
    }

    
    public void addIndex(int index,int val){
        if (index<0 || index>size){
            System.err.println("add index illegal!");
            return;
        }else if (index == 0) addFirst(val);
        else if (index == size) addLast(val);
        else {
            // 在中间位置插入，找到index的前驱节点
            // 找到index索引对应的节点后 写成方法 node
            Node prev = node(index-1);
            // 连接四根线
            Node newNode = new Node(prev,val,prev.next);
            prev.next.prev = newNode;
            prev.next = newNode;
            size++;
        }
    }

    
    public boolean rangeIndex(int index){
        if (index < 0 || index >= size){
            return false;
        }
        return true;
    }

    
    public int get(int index){
        if (rangeIndex(index)){
            return node(index).val;
        }else {
            System.out.println("get index illegal!");
            return -1;
        }
    }

    
    public boolean contains(int val){
        for (Node x = head;x!=null;x=x.next){
            if (x.val==val){
                return true;
            }
        }
        return false;
    }

    
    public int set(int index,int newVal){
        if (rangeIndex(index)){
            Node node = node(index);
            int oldVal = node.val;
            node.val = newVal;
            return oldVal;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    
    private void unlink(Node node){
        // 分治思想
        Node prev = node.prev;
        Node next = node.next;
        // 先处理前驱节点
        if (prev == null){ // 此时是个头节点
            head = next;
        }else{
            // 有前驱
            prev.next = next;
            node.prev = null;
        }
        // 此时接着处理后半边的情况
        if (next == null){ // 此时node是个尾节点
            tail = prev;
        }else{
            next.prev = prev;
            node.next = null;
        }
        size--;
    }

    
    public void removeIndex(int index){
        if (rangeIndex(index)){
            Node node = node(index);
            unlink(node);
        }else{
            System.err.println("remove index illegal!");
        }
    }

    
    public void removeFirst() {
        removeIndex(0);
    }

    
    public void removeLast() {
        removeIndex(size - 1);
    }


    public String toString(){
        String ret = "";
        Node node = head;
        while (node != null){
            ret += node.val + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }

    
    public void removevalueonce(int val){
        // 找到待删除节点
        for (Node x=head;x!=null;x=x.next){
            if (x.val==val){
                unlink(x);
                break;
            }
        }
    }

    
    public void removevalueAll(int val){
        for (Node x=head;x!=null;){
            if (x.val==val){// x是待删除节点
                // next是下一个要判断的节点
                Node next = x.next;
                // 删除之后，x.next = x.prev = null
                unlink(x);
                x=next;
            }else{
                // 继续向后走
                x=x.next;
            }
        }
    }

    }


class Node{
    Node prev;   // 指向前驱节点
    int val;     // 保存具体值
    Node next;   // 指向后继节点

    public Node(int val){
        this.val = val;
    }

    public Node(Node prev,int val,Node next){
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}

测试类 

package seqlist.doublelink;

public class testDoublelinkedList {
    public static void main(String[] args) {
        DoublelinkedList linkedList = new DoublelinkedList();
        linkedList.addLast(2);
        linkedList.addLast(9);
        linkedList.addLast(2);
        linkedList.addLast(2);
        linkedList.addLast(2);
        linkedList.addFirst(7);
        linkedList.addFirst(5);
        linkedList.addIndex(0,3);
        linkedList.addIndex(3,6);
        System.out.println(linkedList);//3->5->7->6->2->9->2->2->2->NULL
        linkedList.removeIndex(3);
        System.out.println(linkedList);//3->5->7->2->9->2->2->2->NULL
        linkedList.removevalueonce(2);
        System.out.println(linkedList);//3->5->7->9->2->2->2->NULL
        linkedList.removevalueAll(2);
        System.out.println(linkedList);//3->5->7->9->NULL
        System.out.println(linkedList.get(1));//5
        linkedList.set(2,10);
        System.out.println(linkedList);//3->5->10->9->NULL
    }
}

---

本小节完^_^