简介:
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的，由一系列结点组成，每个结点除了要存储数据外，还需存储指向后继结点或前驱结点的存储地址。

动态数组有个明显的缺点,可能会造成内存空间的大量浪费,链表不需要提前分配存储空间，元素个数不受限制

链表的设计

单链表
java单链表的代码实现

package com.njf;

public class LinkedList<E> {//泛型
    /**
     * 链表大小
     */
    private int size;
    /**
     * 指向头结点的引用
     */
    private Node<E> first;
    
    private static final int ELEMENT_NOT_FOUND = -1;
    
    private static class Node<E> {//创建节点
        //数据域
        E element;
        //指向后继结点的引用
        Node<E> next;
        public Node(E element, Node<E> next) {//构造函数
            this.element = element;
            this.next = next;
        }
    }
    
    /**
     * 根据索引返回一个节点
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    
    /**
     * 清除所有链表数据
     */
    public void clear() {
        size = 0;
        first = null;
    }

    /**
     * 链表大小
     * @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);
    }

    /**
     * 获取index位置的节点中的数据
     * @param index
     * @return
     */
    public E get(int index) {
        return node(index).element;
    }

    /**
     * 设置index位置节点中的数据
     * @param index
     * @param element
     * @return 原来的节点中的数据
     */
    public E set(int index, E element) {
        //获取当前节点
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;
        return oldElement;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        if (index == 0) {
            first = new Node<>(element, first);
        }else {
            //先获取前一个节点
            Node<E> priviousNode = node(index-1);
            priviousNode.next = new Node<>(element, priviousNode.next);
        }
        size ++;
    }

    /**
     * 删除index位置的节点
     * @param index
     * @return
     */
    public E remove(int index) {
        Node<E> node = first;
        if (index == 0) {
            first = first.next;
        }else {
            Node<E> previousNode = node(index - 1);
            node = previousNode.next;
            previousNode.next = previousNode.next.next;
        }
        size --;
        return node.element;
    }

    /**
     * 查看某个节点元素的索引
     * @param element
     * @return
     */
    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 (node.element.equals(element)) return I;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @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();
    }
}

swift单链表的实现

import UIKit

class LinkedList<E> where E:Equatable{
    fileprivate var size : Int = 0
    fileprivate var first : Node<E>?
    fileprivate let ELEMENT_NOT_FOUND : Int = -1;
    //定义内部节点
    fileprivate class Node<E> where E:Equatable{
        static func == (lhs: Node<E>, rhs: Node<E>) -> Bool {
            return lhs.element == rhs.element
        }
        var element : E
        var next : Node<E>?
        init(element : E){//构造函数
            self.element = element;
        }
    }
    /**
     * 根据索引返回一个节点
     */
    fileprivate func node(index:Int) ->Node<E>{
        //判断index
        rangeCheck(index: index)
        var node : Node<E> = first!
        for _ in 0..<index{
            if node.next != nil {
                node = node.next!
            }
        }
        return node
    }
    
    /**
     * 清除所有链表数据
     */
    public func clear(){
        size = 0
        first = nil
    }

    /**
     * 链表大小
     * @return
     */
    public func linkSize()->Int{
        return size
    }

    /**
     * 链表是否为空
     * @return
     */
    public func isEmpty()->Bool{
        return size == 0
    }

    /**
     * 是否包含某个数据元素
     * @param element
     * @return
     */
    public func contains(element:E) ->Bool{
        return indexOf(element: element) != ELEMENT_NOT_FOUND
    }
 
    /**
     * 添加节点到尾部
     * @param element
     */
    public func add(element : E){
        add(index: size, element: element)
    }

    /**
     * 获取index位置的节点中的数据
     * @param index
     * @return
     */
    public func getElement(index:Int) ->E{
        return node(index: index).element
    }

    /**
     * 设置index位置节点中的数据
     * @param index
     * @param element
     * @return 原来的节点中的数据
     */
    
    public func setElement(index:Int,element:E) ->E{
        //获取当前节点
        let currentNode:Node<E> = node(index: index)
        let oldElement:E = currentNode.element
        currentNode.element = element
        return oldElement
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public func add(index:Int,element:E){
        if index == 0 {//头插法
            let tempNode = Node(element: element)
            tempNode.next = first
            first = tempNode
        }else{
            //获取前一个节点
            let previousNode:Node<E> = node(index: index - 1)
            //当前节点
            let currentNode = Node(element: element)
            currentNode.next = previousNode.next
            previousNode.next = currentNode
        }
        size+=1
    }

    /**
     * 删除index位置的节点
     * @param index
     * @return
     */
    public func remove(index:Int) ->E{
        var currentNode : Node<E> = first!
        if index == 0 {
            first = first?.next
        }else{
            //获取前一个节点
            let previousNode:Node<E> = node(index: index - 1)
            currentNode = previousNode.next!
            previousNode.next = previousNode.next!.next
        }
        size-=1
        return currentNode.element
    }

    /**
     * 查看某个节点元素的索引
     * @param element
     * @return
     */
    public func indexOf(element:E) ->Int{
        var initNode:Node<E> = first!
        if element is NSNull{
            for i in 0..<size{
                if initNode.element is NSNull{
                    return I
                }
                initNode = initNode.next!
            }
        }else{
            for i in 0..<size{
                if initNode.element == element{
                    return I
                }
                initNode = initNode.next!
            }
        }
        return ELEMENT_NOT_FOUND
    }
    
    public func display(){
        var currentNode : Node<E> = first!
        var printStr : String = "size="
        printStr.append("\(size)")
        printStr.append(", [")
        for i in 0..<size{
            if (i != 0) {
                printStr.append(", ");
            }
            printStr.append("\(currentNode.element)")
            if currentNode.next != nil{
                currentNode = currentNode.next!
            }
        }
        printStr.append("]");
        print(printStr)
    }
    
    fileprivate func outOfBounds(index:Int) {
        print("index = \(index) 越界了")
        assert(false)
    }
   
    fileprivate func rangeCheck(index:Int){
        if index<0 || index >= size{
            outOfBounds(index: index)
        }
    }
    
    fileprivate func rangeCheckForAdd(index:Int){
        if index<0 || index > size{
            outOfBounds(index: index)
        }
    }
}

下面是swift调用和显示结果

let list:LinkedList<Int> = LinkedList()
list.add(element: 50)
list.add(element: 30)
list.add(element: 20)
list.add(index: 1, element: 10)
list.display()
let index = list.indexOf(element: 30)
print(index)
let element = list.remove(index: 0)
print(element)
list.display()

size=4, [50, 10, 30, 20]
2
50
size=3, [10, 30, 20]

虚拟头结点

◼ 有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）

public LinkedList() {
    first = new Node<>(null, null);
}

单向循环链表

java代码实现

package com.njf;

public class SingleCycleLinkedList<E> {
    /**
     * 链表大小
     */
    private int size;
    /**
     * 指向头结点的引用
     */
    private Node<E> first;
    
    private static final int ELEMENT_NOT_FOUND = -1;
    
    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 String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(element).append("_").append(next.element);
            return sb.toString();
        }
    }

    /**
     * 根据索引返回一个节点
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    
    /**
     * 清除所有链表数据
     */
    public void clear() {
        size = 0;
        first = null;
    }

    /**
     * 链表大小
     * @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);
    }

    /**
     * 获取index位置的节点中的数据
     * @param index
     * @return
     */
    public E get(int index) {
        return node(index).element;
    }

    /**
     * 设置index位置节点中的数据
     * @param index
     * @param element
     * @return 原来的节点中的数据
     */
    public E set(int index, E element) {
        //获取当前节点
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;
        return oldElement;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        if (index == 0) {
            Node<E> newFirst = new Node<>(element, first);
            Node<E> last = (size == 0) ? newFirst : node(size - 1);
            last.next = newFirst;
            first = newFirst;
        }else {
            //先获取前一个节点
            Node<E> priviousNode = node(index-1);
            priviousNode.next = new Node<>(element, priviousNode.next);
        }
        size ++;
    }

    /**
     * 删除index位置的节点
     * @param index
     * @return
     */
    public E remove(int index) {
        Node<E> node = first;
        if (index == 0) {
            if (size == 1) {
                first = null;
            }else {
                Node<E> last = node(size - 1);
                first = first.next;
                last.next = first;
            }
        }else {
            Node<E> previousNode = node(index - 1);
            node = previousNode.next;
            previousNode.next = previousNode.next.next;
        }
        size --;
        return node.element;
    }

    /**
     * 查看某个节点元素的索引
     * @param element
     * @return
     */
    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 (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @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);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}

下面是调用和显示结果

package com.njf;

public class Main {
    
    static void testList(SingleCycleLinkedList<Integer> list) {
        list.add(11);
        list.add(22);
        list.add(33);
        list.add(44);

        list.add(0, 55); // [55, 11, 22, 33, 44]
        list.add(2, 66); // [55, 11, 66, 22, 33, 44]
        list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

        list.remove(0); // [11, 66, 22, 33, 44, 77]
        list.remove(2); // [11, 66, 33, 44, 77]
        list.remove(list.size() - 1); // [11, 66, 33, 44]

        Asserts.test(list.indexOf(44) == 3);
        Asserts.test(list.contains(33));
        Asserts.test(list.get(0) == 11);
        Asserts.test(list.get(1) == 66);
        Asserts.test(list.get(list.size() - 1) == 44);
        
        System.out.println(list);
    }
    
    public static void main(String[] args) {
        testList(new SingleCycleLinkedList<>());
    }
}

size=4, [11_66, 66_33, 33_44, 44_11]

数据结构和算法动态可视化 (Chinese)