【Java学习—(12)小学生看了都能学会的双向链表】

(点击跳转即可哦)

java学习专栏

双向链表

单链表：单向链表，默认只能从链表的头部遍历到链表的尾部。实际的应用很少见，太局限，只能从头遍历到尾部

双向链表：对于该链表中的任意节点，即可通过该节点向后走，也可以通过该节点向前走。双向链表在实际工程中应用非常广泛，使用链表这个结构的首选

双向链表的节点

每个节点既保存了下一个节点的地址，也保存了上一个节点的地址，这样的话，就可以通过任意的节点从前向后或者从后向前

class DoubleNode{
	int val; //该节点存储的值
    DoubleNode pre; //前一个节点的地址
    DoubleNode next; //后一个节点的地址
    public DoubleNode(){}
    public DoubleNode(int val){
        this.val = val;
    }
    public DoubleNode(DoubleNode pre,int Val, DoubleNode next){
        this.pre = pre;
        this.val = val;
        this.next = next;
    }
}

双向链表的属性：

int size -> 保存链表有效节点的个数

DoubleNode head -> 头节点的地址

DoubleNode tail -> 尾节点的地址

public class DoubleSingleLinkedList {
    private int size;
    private DoubleNode head;
    private DoubleNode tail;
}

头插法：

1 当链表为空时，此时头节点是null,尾节点也为空。

2 若链表不为空时，

链表 head 的pre 指向新的节点的地址，

新节点的next指向 head,

最后新的节点变为新的头节点。

    //头插法
    public void addHead(int val){
        DoubleNode node = new DoubleNode(val);
        if(head == null){
            tail = node;
        }else {
            head.pre = node;
            node.next = head;
        }
        head = node;
        size++;
    }

根据索引插入节点，既然是根据索引插入节点，首先要判断索引的合法性，

        if(index < 0 || index > size){
            System.out.println("index = " + index + ",该索引值不合法");
            return;
        }

再判断插入节点的几个特殊位置，是在头节点插入，还是在尾节点插入，还是在中间节点插入。

    //根据索引进行插入节点
    public void addIndex(int index, int val){
        if(index < 0 || index > size){
            System.out.println("index = " + index + ",该索引值不合法");
            return;
        }
        if(index == 0){ //头节点插入
            addHead(val);
        }else if(index == size){ //尾节点插入
            DoubleNode newNode = new DoubleNode(tail,val,null);
            tail.next = newNode;
            tail = newNode;
            size++;
        }else {
            //要插入的节点
            DoubleNode newNode = new DoubleNode(val);
            //index位置的节点
            DoubleNode indexNode = fNode(index);
            //index位置的前驱节点
            DoubleNode preNode = indexNode.pre;
            preNode.next = newNode;
            newNode.pre = preNode;
            newNode.next = indexNode;
            indexNode.pre = newNode;
            size++;
        }
    }

在中间节点插入时，调用了一个私有方法 fNode(int index); 这个方法用于返回 index 位置节点的地址。

    
    private DoubleNode fNode(int index){
        if(index < size/2){
            DoubleNode x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            //此时x存储的是index位置 节点的地址
            return x;
        }else {
            DoubleNode x = tail;
            for (int i = size-1; i > index; i--) {
                x = x.pre;
            }
            return x;
        }
    }

尾节点插入，这个就很好实现了，直接调用在中间节点插入的方法。

//尾插
public void addLast(int val){
    addIndex(size,val);
}

查询

1 根据索引查找，返回索引位置的值,若索引不合法，则输出索引不合法，返回-1

调用了fNode方法

    //根据索引查找，返回索引位置的值
    public int findIndex(int index){
        if(pdIndexLegal(index)){
            DoubleNode nodeIndex = fNode(index);
            return nodeIndex.val;
        }
        System.out.println("index = " + index + ",索引不合法");
        return -1;
    }

2 根据值查找第一个val值的索引，返回索引值，没有这个值，输出没有这个值，并输出-1

public int findVal(int val){
    int index = 0;
    for (DoubleNode x = head;x != null; x = x.next){
        if(x.val == val){
            return index;
        }
        index++;
    }
    System.out.println("没有找到这个值");
    return -1;
}

修改：

1 根据索引修改索引位置的值

public boolean setIndex(int index,int newVal){
    if(pdIndexLegal(index)){
        DoubleNode indexNode = fNode(index);
        indexNode.val = newVal;
        return true;
    }
    return false;
}

2 找到第一个值为Val,修改此节点的值

public boolean setVal(int val, int newVal){
    if (findVal(val) != -1){
        int index = findVal(val);
        DoubleNode nodeIndex = fNode(index);
        nodeIndex.val = newVal;
        return true;
    }
    return false;
}

删除：

1 删除index位置的节点

    public boolean delIndex(int index){
        if(pdIndexLegal(index)){
            delNode(fNode(index));
            return true;
        }
        return false;
    }

调用了delNode方法，该方法传入一个节点，删除该节点，无返回值。

private void delNode(DoubleNode node){
    if(head == null || tail == null){ //传入一个空节点
        return;
    }
    if(head == node){ //头节点删除
        head = head.next;
        head.pre = null;
    }else if(tail == node){//尾节点删除
        tail = tail.pre;
        tail.next = null;
    }else { //中间节点删除
        DoubleNode preNode = node.pre;
        DoubleNode nextNode = node.next;
        preNode.next = nextNode;
        node.pre = null;
        nextNode.pre = preNode;
        node.next = null;
    }
}

2 删除头节点

public boolean delHead(){
    if(head == null){
        return false;
    }
    delNode(head);
    return true;
}

3 删除尾节点

public boolean delLast(){
    if(tail == null){
        return false;
    }
    delNode(tail);
    return true;
}

4 删除第一个值为Val的节点

public boolean delVal(int val){
    if(findVal(val) != -1){
        int index = findVal(val);
        delNode(fNode(index));
        return true;
    }
    return false;
}

5 删除所有值为Val的节点

public boolean delAllVal(int val){
    if(head == null){
        return false;
    }
    for (DoubleNode x = head;x != null;){
        if(x.val == val){
            DoubleNode y = x.next;
            delNode(x);
            x = y;
        }else {
            x = x.next;
        }
    }
    return true;
}

打印数据的方法

    @Override
    public String toString() {
        String ret = "";
        for (DoubleNode x = head;x != null; x = x.next){
            ret += x.val;
            ret += "->";
        }
        ret += "null";
        return ret;
    }
}

附上源代码：

package dynamic_array;

public class DoubleList {
    int size;
    DoubleNode head;
    DoubleNode tail;
    
    public void addHead(int val){
        DoubleNode node = new DoubleNode(val);
        if(head == null){
            tail = node;
        }else {
            head.pre = node;
            node.next = head;
        }
        head = node;
        size++;
    }
    //根据索引进行插入节点
    public void addIndex(int index, int val){
        if(index < 0 || index > size){
            System.out.println("index = " + index + ",该索引值不合法");
            return;
        }
        if(index == 0){ //头节点插入
            addHead(val);
        }else if(index == size){ //尾节点插入
            DoubleNode newNode = new DoubleNode(tail,val,null);
            tail.next = newNode;
            tail = newNode;
            size++;
        }else {
            //要插入的节点
            DoubleNode newNode = new DoubleNode(val);
            //index位置的节点
            DoubleNode indexNode = fNode(index);
            //index位置的前驱节点
            DoubleNode preNode = indexNode.pre;
            preNode.next = newNode;
            newNode.pre = preNode;
            newNode.next = indexNode;
            indexNode.pre = newNode;
            size++;
        }
    }


    //尾插
    public void addLast(int val){
        addIndex(size,val);
    }
    //根据索引查找，返回索引位置的值
    public int findIndex(int index){
        if(pdIndexLegal(index)){
            DoubleNode nodeIndex = fNode(index);
            return nodeIndex.val;
        }
        System.out.println("index = " + index + ",索引不合法");
        return -1;
    }
    //根据值查找该位置的索引，返回索引值，没有这个值，输出没有这个值，并输出-1
    public int findVal(int val){
        int index = 0;
        for (DoubleNode x = head;x != null; x = x.next){
            if(x.val == val){
                return index;
            }
            index++;
        }
        System.out.println("没有找到这个值");
        return -1;
    }
    //根据索引修改索引位置的值
    public boolean setIndex(int index,int newVal){
        if(pdIndexLegal(index)){
            DoubleNode indexNode = fNode(index);
            indexNode.val = newVal;
            return true;
        }
        return false;
    }
    //找到第一个值为Val,修改此节点的值
    public boolean setVal(int val, int newVal){
        if (findVal(val) != -1){
            int index = findVal(val);
            DoubleNode nodeIndex = fNode(index);
            nodeIndex.val = newVal;
            return true;
        }
        return false;
    }
    //删除index位置的节点
    public boolean delIndex(int index){
        if(pdIndexLegal(index)){
            delNode(fNode(index));
            return true;
        }
        return false;
    }
    //删除当前节点
    private void delNode(DoubleNode node){
        if(head == null || tail == null){
            return;
        }
        if(head == node){
            head = head.next;
            head.pre = null;
            size--;
        }else if(tail == node){
            tail = tail.pre;
            tail.next = null;
            size--;
        }else {
            DoubleNode preNode = node.pre;
            DoubleNode nextNode = node.next;
            preNode.next = nextNode;
            node.pre = null;
            nextNode.pre = preNode;
            node.next = null;
            size--;
        }
    }
    //删除头节点
    public boolean delHead(){
        if(head == null){
            return false;
        }
        delNode(head);
        return true;
    }
    //删除尾节点
    public boolean delLast(){
        if(tail == null){
            return false;
        }
        delNode(tail);
        return true;
    }
    //删除第一个值为Val的节点
    public boolean delVal(int val){
        if(findVal(val) != -1){
            int index = findVal(val);
            delNode(fNode(index));
            return true;
        }
        return false;
    }
    //删除所有值为Val的节点
    public boolean delAllVal(int val){
        if(head == null){
            return false;
        }
        for (DoubleNode x = head;x != null;){
            if(x.val == val){
                DoubleNode y = x.next;
                delNode(x);
                x = y;
            }else {
                x = x.next;
            }
        }
        return true;
    }
    
    private DoubleNode fNode(int index){
        if(index < size/2){
            DoubleNode x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            //此时x存储的是index位置 节点的地址
            return x;
        }else {
            DoubleNode x = tail;
            for (int i = size-1; i > index; i--) {
                x = x.pre;
            }
            return x;
        }
    }
    
    private boolean pdIndexLegal(int index){
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }
    @Override
    public String toString() {
        String ret = "";
        for (DoubleNode x = head;x != null; x = x.next){
            ret += x.val;
            ret += "->";
        }
        ret += "null";
        return ret;
    }
}

要是对大家有所帮助的话，请帮我点个赞吧。

【Java学习—(12)小学生看了都能学会的双向链表】

Java相关栏目本月热门文章