算法通关村第一关-链表青铜挑战笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第一关-链表青铜挑战笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链表

平时我们一般都是用数组，每个数组都会有一个相对应的索引，这样就使得数组能够方便的调用出对应索引得到需要的数据，但是这也造成了一个问题，那就是不好在数组中插入或者删除一个数据，例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就需要考虑一个问题，arr的大小是否足够存下，会不会超出数组大小，再就是添加数据的繁琐，我们需要先将4和5存起来，再将3放原先4的位置，4放5的位置，5再往后放。这样就造成了没必要的计算量。这时候我们就可以使用链表来存储。

链表其实和数组很像，都是按照顺序位置都存储数据再进行调用，但是存储的方法完全不同。数组中都是每个数据存在对应的索引位置，而链表是相对位置。

数组如图算法通关村第一关-链表青铜挑战笔记,java,开发语言

链表如图算法通关村第一关-链表青铜挑战笔记,java,开发语言

从图中能看出链表的连接是靠上一个next所存储的位置，所以不需要考虑大小问题，也不需要考虑数据插入和删除,那么该如何创建链表。

首先我们需要创建节点类

public class Node{
    int var;
    //创建var用来存储数据
    Next next;
    //next用来存储下一个节点
    public Node(int var){
        this.var = var;
    }
    //构造方法传值
}

创建链表

public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6};
        Node node = initLinkedList(a);
    }
    
private static Node initLinkedList{
    Node head =null;
    //将头设为空
    Node newNode0 = new Node(a[0]);
}

这就是一个简单的链表，设置了头，创建了newNode0并给了值a[0]

既然创建了链表，可是链表只有一个并不能存储多个数据，这时候就要创建多个链表并进行连接了

private static Node initLinkedList(int[] a){
    Node head = null;

    Node newNode1 = new Node(a[1]);
    Node newNode0 = new Node(a[0]);
    Node newNode2 = new Node(a[2]);
    
    head = newNode0;
    //将newNode0设置为头也就是开始
    newNode0.next = newNode1;
    //用next来对链表进行连接
    newNode1.next = newNode2;


    return head;
}

可以通过debug右键Evaluate 来进行查看

算法通关村第一关-链表青铜挑战笔记,java,开发语言

这就是一个简单的链表，但是这个链表存在一个问题就是每次读取数据只能往后走并不往前读取数据，如果需要读取前面的数据则需要重头开始浪费大量时间，这时候就需要双向链表。算法通关村第一关-链表青铜挑战笔记,java,开发语言

能从图中看出多了一个peev来连接上一个节点，这也就是双向链表，代码如下

首先在节点类中添加一个prev。

public class Node {
    public int var;
    public Node next;
    public Node prev;

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

再进行添加prev前一个值

private static Node initLinkedList(int[] a){
    Node head = null;

    Node newNode0 = new Node(a[0]);
    Node newNode1 = new Node(a[1]);
    Node newNode2 = new Node(a[2]);
     
    head = newNode0;
    newNode0.next = newNode1;
    newNode1.next = newNode2;

    newNode2.prev = newNode1;
    newNode1.prev = newNode0;
    //添加前一个节点数据
    return head;
}

这就是个简单的双向链表。可是讲了半天并没有写出链表方便的增删改，那就从增开始。

因为链表是通过next来确认下一个节点，那么只需要在最后的数据添加一个next

private static Node initLinkedList(int[] a){
    Node head = null;

     Node newNode0 = new Node(a[0]);
     Node newNode1 = new Node(a[1]);
     Node newNode2 = new Node(a[2]);
    
    head = newNode0;
    newNode0.next = newNode1;
    newNode1.next = newNode2;

    newNode2.prev = newNode1;
    newNode1.prev = newNode0;
    
    //添加当前节点的上一个节点prev 和 上一个节点的next
    Node newNode3 = new Node(a[3]);
    newNode2.next = newNode3;
    newNode3.prev = newNoed2;
    
    return head;
}

算法通关村第一关-链表青铜挑战笔记,java,开发语言

那么删除同理

private static Node initLinkedList(int[] a){ Node head = null;

 Node newNode0 = new Node(a[0]);
 Node newNode1 = new Node(a[1]);
 Node newNode2 = new Node(a[2]);

head = newNode0;
newNode0.next = newNode1;
newNode1.next = newNode2;

newNode2.prev = newNode1;
newNode1.prev = newNode0;

//删除2节点的上一个节点prev 和 上一个节点的next
newNode2.prev = newNode0;
newNode0.next = newNode2;

return head;
}

算法通关村第一关-链表青铜挑战笔记,java,开发语言