数据结构与算法--链表的定义

数据结构与算法--链表的定义

这两天又被链表困难到了，虽然之前了解过，但是自己书写起来才发现各种细节没有注意到。依旧是参照leetcode（https://leetcode-cn.com/problems/design-linked-list/）和《代码随想录》（https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC），这次主要针对于代码书写中定链表位置时可能出现的pre.next.next这种链接了很多next的情况进行了汇总和修改，按照题目要求，书写了单链表和双链表的代码。其中，用pre, cur, nex分别指代所定位节点（即index指定的那个节点）的前一个、当前节点、后一个节点；用prev, next 代表一个节点的前后指向，其余具体思路见注释。
题目：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
代码：
（单链表）

//定义节点
class Node {
    public int val;
    public Node next;
    public Node(int val, Node next) {
        this.next = next;
        this.val = val;
    }
}
//构造链表
class MylinkedList {
    private int size;
    //虚拟头结点
    private Node head;
	//初始化链表信息
    public MylinkedList() {
        size = 0;
        head = new Node(0,null);
    }
    //获取第index个节点的值
    public int get(int index) {
        if(index < 0 || index >= size) {
            return -1;
        }
        //由于插入值是在pre-cur之间并且设有虚拟节点head，从代码清晰度和逻辑性上讲，找到index对应的pre更方便，以下代码统一用这样的思路和格式。
        Node pre = head;
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node cur = pre.next;
        return cur.val;
    }
    //头和尾直接按照index的不同来插入
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) {
            return ;
        }
        if(index < 0) {
            index = 0;
        }
        Node pre = head;
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        //找到正确的pre和cur节点就很清晰 pre.next = newNode, newNode.next = cur
        Node cur = pre.next;
        Node newNode = new Node(val, cur);
        pre.next = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) {
            return ;
        }
        Node pre = head;
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        //Java语言有内存回收机制，删除节点就直接pre.next = cur.next让pre.next跳过cur指向cur.next
        Node cur = pre.next;
        pre.next = cur.next;
        size--;
    }
}

结果：

（双链表）

class Node {
    public int val;
    //双链表的节点主要变成了前和后的双向指向
    public Node next, prev;
    public Node(int val, Node prev, Node next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

class MylinkedList {
    public int size;
    //增设了尾部节点
    public Node head;
    public Node tail;

    public MylinkedList() {
        size = 0;
        head = new Node(0, null, null);
        tail = new Node(0, null, null);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
        if(index < 0 || index >= size) {
            return -1;
        }
		//选择从头遍历和从尾遍历
		//i<多少是需要盘逻辑的，前面单链表中对于从头遍历已经比较明了，从尾遍历带入特殊情况来确定也很明了
        if(index <= (size + 1) / 2) {
            Node pre = head;
            for(int i = 0; i < index; i++) {
                pre = pre.next;
            }
            Node cur = pre.next;
            return cur.val;
        } else {
        	//这里丛尾开始遍历就是用nex了
            Node nex = tail;
            for(int i = 0; i < (size - index - 1); i++) {
                nex = nex.prev;
            }
            Node cur = nex.prev;
            return cur.val;
        }
    }
    
    public void addAtHead(int val) {
        Node pre = head;
        Node cur = pre.next;
        Node newNode = new Node(val, pre, cur);
        pre.next = newNode;
        cur.prev = newNode;
        size++;
    }
    
    public void addAtTail(int val) {
        Node nex = tail;
        Node cur = nex.prev;
        Node newNode = new Node(val, cur, nex);
        cur.next = newNode;
        nex.prev = newNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) {
            return ;
        }
        if(index < 0) {
            index = 0;
        }
        Node pre = head;
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        //双链表在此处的代码比单链表更加清晰
        Node cur = pre.next;
        //newNode的定义语句直接清晰地显示出位置关系
        Node newNode = new Node(val, pre, cur);
        pre.next = newNode;
        cur.prev = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) {
            return ;
        }
		//删除语句的查询方式和get函数相差无多
        if(index <= (size + 1) / 2) {
            Node pre = head;
            for(int i = 0; i < index; i++) {
                pre = pre.next;
            }
            //就是删节点时候有点麻烦，但很清晰的是，得到pre-cur-nex三个节点，将pre.next和nex.prev重新赋值就行了。
            Node cur = pre.next;
            Node nex = cur.next;
            nex.prev = pre;
            pre.next = nex;
            
        } else {
            Node nex = tail;
            for(int i = 0; i < (size - index - 1); i++) {
                nex = nex.prev;
            }
            Node cur = nex.prev;
            Node pre = cur.prev;
            pre.next = nex;
            nex.prev = pre;
        }
        size--;
    }
}

结果：

分析：
可以看出双链表的执行时间更短，主要是因为双向的特性，此处的双链表指定位置赋值还没有充分利用双向的特性，速度未能达到顶尖。