数据结构与算法基础入门——手写链表（二）

1、什么是链表，链表的定义？

通俗的说就是通过指针将一组零散的内存块串联在一起。

其中，我们把内存块称为链表的 "节点"。


为了将所有的节点串在一起，每个链表的节点除了存储数据之外，还要记录下一个节点的地址。

• 单向链表

  对单链表来说有两个节点比较特殊分别是第一个被称为头节点和最后一个尾节点，头节点又用来记录链表的基地址，有了它我们就可以遍历整个链表，而尾节点的特殊是的它的指针指的不是下一个节点而是空地址null,表示链表上的最后一个节点。
  

  
  

• 双向链表
  双向链表，顾名思义，它支持两个方向，每个节点不止有一个指针next 指向下一个节点，还有个前驱指针prev指向前面的节点。
  

  
  

  双向链表需要额外的两个空间来存储前驱节点和后驱的地址。
  

  
  

  所以双向链表比单向的多占空间，但是因为支持双向遍历，所以比单向链表更灵活，查询更快。
  

  
  

  
  如图：
  

• 分析对比数组优缺点：
  能够很方便的增加/删除节点。
  

  
  

  数组的在删除和新增数据时，需要移动其它数据项。
  

  
  

  
  在查询的时候没有数组快，数组可以直接根据索引直接定位。
  

  
  

  而链表无论时单向链表还是双向链表都需要一个节点一个节点的进行查找。
  

  
  

• 从内存存储看:
  数组是从栈中分配空间，并且按顺序存储，一开始就需要定义好，这样会导致内存浪费。
  

  
  

  也会导致下标越界。
  

  
  

  
  链表是从堆中分配空间，无序随机。
  

  
  

  可以动态，管理不好会导致内存溢出。
  

  
  

  
  

public class SingelLinkedList {
    private ListNode head;
    private int size = 0;
    class ListNode{

         String value;

        ListNode next;

        ListNode(String value){
            this.value = value;
            this.next = null;
        }
    }
    public void inserthead(String value){

        ListNode listNode = new ListNode(value);
        listNode.next = head;
        head = listNode;

    }
    public void inserCenter(String value,int index){
        if(index == 0){
            inserthead(value);
        } else {
            ListNode cur = head;
            for (int i = 1; i < index; i++) {
                cur = cur.next;
            }
            ListNode listNode = new ListNode(value);
            listNode.next = cur.next;
            cur.next = listNode;
        }
    }
    public void deleteHead(){
        head = head.next;
    }
    public void deleteNth(int index){
        if(index == 0){
            deleteHead();
        }else{
            ListNode cur = head;
            for (int i = 1; i < index; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
    }
    public void find(String data){
        ListNode cur = head;
        while(cur != null){
            if(cur.value == data) break;
            cur = cur.next;
        }
    }
    public void print(){
        ListNode cur = head;
        while(cur != null){
            System.out.println(cur.value+" ");
            cur = cur.next;
        }
    }
    public static void main(String[] args) {
        SingelLinkedList linkedList = new SingelLinkedList();
        linkedList.inserthead("我是头");
        linkedList.inserCenter("我是第二",1);
        linkedList.inserCenter("我是第三",2);
        linkedList.deleteNth(1);
        linkedList.find("我是第二");
        linkedList.print();
    }
}

public class DoubleLinkedList {
    DNode head;
    DNode tail;
    DoubleLinkedList() {
        head = null;
        tail = null;
    }
    public void insertHead(String data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            tail = newNode;
        } else {
            head.pre = newNode;
            newNode.next = head;
        }
        head = newNode;

    }
    public void insertNth(String data,int index){
        if(index == 0){
            insertHead(data);
        } else {
            DNode cur = head;
            DNode listNode = new DNode(data);
            for (int i = 1; i < index; i++) {
                if(cur.next == null){
                    cur.next = listNode;
                    listNode.pre = cur;
                    return;
                }
                cur = cur.next;
            }
            listNode.next = cur.next;
            cur.next = listNode;
            listNode.pre = cur.pre;
            cur.pre = listNode;
        }
    }
    public void deleteHead(int index){
        if(head == null){
            System.out.println("链表为空");
            return;
        }
        if(index == 0){
            if(head.next == null){
                head = null;
                return;
            }
            head = head.next;
            head.pre = null;
            return;
        }
        DNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        if(cur.next == null){
            cur.pre.next = null;
            return;
        }
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
    }
    public void print(){
        if(head == null){
            System.out.println("链表为空");
            return;
        }
        DNode dNode = head;
        while (dNode!=null){
            if(dNode.next == null){
                System.out.println(dNode.value);
                return;
            }
            System.out.println(dNode.value);
            dNode=dNode.next;
        }
    }
    class DNode{
        String value;
        //后驱指针
        DNode next;
        //前驱指针
        DNode pre;
        DNode(String value){
            this.value = value;
            this.next = null;
            this.pre = null;
        }
    }
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.insertHead("1");
        doubleLinkedList.insertNth("2",2);
        doubleLinkedList.insertNth("3",3);
        doubleLinkedList.print();
        doubleLinkedList.deleteHead(3);
        doubleLinkedList.print();
    }

}

拓展：

LRU（The Least Recently Used，最近最久未使用算法）是一种常见的缓存算法，在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。

LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。

因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。

利用链表实现LRU算法思路：
1、遍历链表，找到后删除当前节点，然后把当前节点插入在头节点。

2、找不到，判断是否还有空间，有空间插入头，没有空间删除最后一个，再插入头节点。