链表 (Linked List)

• 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

  
  1.png
• 可以办到需要多少内存就申请多少内存，避免内存空间大量浪费

链表设计

• 结构 2.png

• 接口设计 3.png

• 代码实现（java)

List接口

package com.jxs;

public interface List<E> {
    
    static final int ELEMENT_NOT_FOUND = -1;
    
    /**
     * 清除所有元素
     */
    void clear();

    /**
     * 元素的数量
     * @return
     */
    int size();
    
    /**
     * 是否为空
     * @return
     */
    boolean isEmpty();
    
    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    boolean contains(E element);
    
    /**
     * 添加元素到尾部
     * @param element
     */
    void add(E element);
    
    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    E get(int index);
    
    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素
     */
    E set(int index,E element);
    
    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    void add(int index,E element);
    
    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    E remove(int index);
    
    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    int indexOf(E element);
    
}
    

AbstractList类

package com.jxs;

public abstract class AbstractList<E> implements List<E>{
    
    /**
     * 元素的数量
     */
    protected int size;
    
    /**
     * 元素的数量
     * @return
     */
    public int size() {
        
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        
        return size == 0;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        
        return indexOf(element) != ELEMENT_NOT_FOUND;
        
    }
    
    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element) {
        
        add(size, element);
    }
    
    protected void outOfBounds(int index) {
        
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        
    }
    
    protected void rangeCheck(int index) {
        if(index <0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    
    protected void rangeCheckForAdd(int index) {
        if(index <0 || index > size) {
            outOfBounds(index);
        }
    }

}

LinkedList类

package com.jxs;

public class LinkedList<E> extends AbstractList<E>{
    
    
    private Node<E> first;
    
    private static class Node<E>{
        
        E element;
        Node<E> next;
        public Node(E element, Node<E> next) {
            
            this.element = element;
            this.next = next;
        }
        
    }
    

    @Override
    public void clear() {
        
        size = 0; 
        first = null;
        
    }
    
    @Override
    public E get(int index) {
        
        return node(index).element;
    }

    
    @Override
    public E set(int index, E element) {
        
    
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        
        return old;
    }


    
    @Override
    public void add(int index, E element) {
        
        rangeCheckForAdd(index);
    
        if(index == 0) {
            
            first = new Node<>(element, first);
            
        }else {
            
            Node<E> prev = node(index - 1);
            prev.next =  new Node<>(element, prev.next);
        }
        
        size++;
        
    }
    
    
    @Override
    public E remove(int index) {
        
        rangeCheck(index);
        
        Node<E> node = first;
        if(index == 0) {
            first = first.next;
        
        }else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }


    

    @Override
    public int indexOf(E element) {
        
        if(element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if(node.element == null) return i;
                node = node.next;
            }
            
        }else {
            
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if(element.equals(node.element)) return i;
                node = node.next;
            }
        }
        
        return ELEMENT_NOT_FOUND;
    }

    

    
    
    private Node<E> node(int index) {
        
        rangeCheck(index);
        
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        
        return node;
    }



    @Override
    public String toString() {
        
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if(i != 0) {
                string.append(", ");
            }
            
            string.append(node.element);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
    
}

Main函数调用

package com.jxs;

public class Main {

    public static void main(String[] args) {
        
        List<Integer> list = new LinkedList<>();
        list.add(20);
        list.add(0, 10);
        list.add(30);
        list.add(list.size(), 40);
        
        list.remove(1);
        
        System.out.println(list);
    }

}

lettcode

1.删除链表中的节点

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

4.png 5.png

java代码实现

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}   

2.反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

6.png

• 递归

7.png

java代码实现

public ListNode reverseList(ListNode head) {
         
     if(head == null || head.next == null) return head;

     ListNode newHead = reverseList(head.next); 
     head.next.next = head;
     head.next = null;
         
     return newHead;
        
}

• 循环（while循环，每次把节点指向上一个节点）

java代码实现

public ListNode reverseList2(ListNode head) {
         
         if(head == null || head.next == null) return head;

         ListNode newHead = null; 
         while (head != null) {
             ListNode tmp = head.next;
             head.next = newHead;
             newHead = head;
             head = tmp;
         }
    
         return newHead;
        
}

3.环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

7.png

快慢指针，相当于两人在赛道跑步，速度快的总会追上速度慢的。

java代码实现

 public boolean hasCycle(ListNode head) {
            
    if(head == null || head.next == null) return false;
         
     ListNode slow = head;
     ListNode fast = head.next;
         
    while(fast != null && fast.next != null) {
            
        slow = slow.next;
        fast = fast.next.next;
             
        if (slow == fast) return true;
     }
         
    return false;
     
}