安科网

数据结构与算法 | 线性表 —— 链表

ifwinds

ifwinds

2019-06-30

关注 关注

数据结构与算法 | 线性表 —— 链表

原文链接: https://wangwei.one/posts/jav...

链表

定义

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

<!--more-->

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。这种结构成为 "单向链表"。

数据结构与算法 | 线性表 —— 链表

在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。

数据结构与算法 | 线性表 —— 链表

当单向链表的尾部数据指向头部数据时，就构成了单向循环链表。

数据结构与算法 | 线性表 —— 链表

当双向链表的头部和尾部相互指向时，就构成了双向循环链表。

数据结构与算法 | 线性表 —— 链表

单向链表

单向链表在插入元素、删除元素时，需要获取前驱元素，需要从head开始遍历，时间复杂度为O(n)。

根据index查询对应元素，也需要从head开始遍历，时间复杂度为O(n)。

代码实现

package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Single Linked List
 *
 * @author https://wangwei.one
 * @date 2018/12/25
 */
public class SingleLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size = 0;
    /**
     * head node
     */
    private Node<T> head;
    /**
     * tail node
     */
    private Node<T> tail;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(index, element);
        }
    }

    /**
     * Add Last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        Node<T> last = tail;
        Node<T> newNode = new Node<>(null, element);
        tail = newNode;
        // if linked list is empty
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param index
     * @param element
     * @return
     */
    private boolean addBefore(int index, T element) {
        checkPositionIndex(index);
        // prev node
        Node<T> prev = null;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }
        // current node
        Node<T> current = x;
        // new node
        Node<T> newNode = new Node<>(current, element);
        // if current node is head
        if (prev == null) {
            head = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * remove element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        Node<T> prev = null;
        Node<T> x = head;
        if (element == null) {
            while (x != null && x.element != null) {
                prev = x;
                x = x.next;
            }
        } else {
            while (x != null && !x.element.equals(element)) {
                prev = x;
                x = x.next;
            }
        }

        // if this linked is null OR don't find element
        if (x == null) {
            return false;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }
        // if delete node is tail
        if (next == null) {
            tail = prev;
        }

        // for GC
        x.element = null;
        x = null;

        size--;
        return true;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        Node<T> prev = null;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }

        // if linked is empty
        if (x == null) {
            return null;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }

        // if delete node is tail
        if (next == null) {
            tail = prev;
        }
        size--;
        return x.element;
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return old element
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        Node<T> node = node(index);
        T oldElement = node.element;
        node.element = element;
        return oldElement;
    }
    
    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        Node<T> node = node(index);
        return node == null ? null : node.element;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    /**
     * check index
     *
     * @param index
     */
    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        if (element == null) {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element == null) {
                    return true;
                }
            }
        } else {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element.equals(element)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Linked List Node
     *
     * @param <T>
     */
    private class Node<T> {
        private Node<T> next;
        private T element;

        public Node(Node<T> next, T element) {
            this.next = next;
            this.element = element;
        }
    }
}
源代码

双向链表

相比于单向链表，双向链表多了一个前驱指针，在查找前驱节点时，时间复杂度降低为了O(1)。

通过index查询，删除某个node节点，时间复杂度都降为了O(1)。代码如下：

代码实现

package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Doubly Linked List
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2018/04/28
 */
public class DoublyLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size = 0;
    /**
     * head element
     */
    private Node<T> head = null;
    /**
     * tail element
     */
    private Node<T> tail = null;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(element, node(index));
        }
    }

    /**
     * Add Last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        final Node<T> last = tail;
        Node<T> newNode = new Node<>(last, element, null);
        tail = newNode;
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param element
     * @param target
     * @return
     */
    private boolean addBefore(T element, Node<T> target) {
        Node<T> prev = target.prev;
        Node<T> newNode = new Node<>(prev, element, target);
        target.prev = newNode;
        if (prev == null) {
            head = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * remove node by element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        if (element == null) {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<T> x = head; x != null; x = x.next) {
                if (element.equals(x.element)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * remove node by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        return unlink(node(index));
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        if (index < (size >> 1)) {
            Node<T> x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<T> x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    /**
     * unlink node
     *
     * @param node
     */
    private T unlink(Node<T> node) {
        final T element = node.element;
        final Node<T> prev = node.prev;
        final Node<T> next = node.next;

        // if unlink is head
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            // clear prev
            node.prev = null;
        }

        // if unlink is tail
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

        node.element = null;
        size--;
        return element;
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        Node<T> oldNode = node(index);
        T oldElement = oldNode.element;
        oldNode.element = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        Node<T> node = node(index);
        return node == null ? null : node.element;
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        if (element == null) {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element == null) {
                    return true;
                }
            }
        } else {
            for (Node<T> x = head; x != null; x = x.next) {
                if (element.equals(x.element)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * node
     *
     * @param <T>
     */
    private class Node<T> {

        private T element;
        private Node<T> prev;
        private Node<T> next;

        public Node(Node<T> prev, T element, Node<T> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }

}
源代码

单向循环链表

与单向链表一样，在寻找前驱节点时，需要遍历整个链表，时间复杂度为O(n).

在第一次添加元素时，特别注意，head与tail为同一节点，并且需要自指向。

package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Singly Circular Linked List
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2018/05/03
 */
public class SinglyCircularLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size = 0;
    /**
     * head node
     */
    private Node<T> head = null;
    /**
     * tail node
     */
    private Node<T> tail = null;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(index, element);
        }
    }

    /**
     * Add Last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        final Node<T> last = tail;
        Node<T> newElement = new Node<>(element, head);
        tail = newElement;
        if (last == null) {
            head = newElement;
            // we need linked itself when add an element first
            tail.next = head;
        } else {
            last.next = newElement;
        }
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param element
     * @param element
     * @return
     */
    private boolean addBefore(int index, T element) {
        checkPositionIndex(index);
        // prev node, start with tail
        Node<T> prev = tail;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }
        // current node
        Node<T> current = x;
        // new node
        Node<T> newNode = new Node<>(element, current);
        if (index == 0) {
            head = newNode;
        }
        prev.next = newNode;
        size++;
        return true;
    }

    /**
     * remove node by element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        // start with tail
        Node<T> prev = tail;
        // start with head
        Node<T> x = head;
        // start with index -1
        int prevIndex = -1;

        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                break;
            }
            if (element != null && element.equals(x.element)) {
                break;
            }
            prev = x;
            x = x.next;
            prevIndex = i;
        }

        // if this linked list is empty
        if (x == null) {
            return false;
        }

        // if don't match element
        if (prevIndex == size - 1) {
            return false;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (prevIndex == -1) {
            head = next;
        }

        // if delete node is tail
        if (prevIndex == size - 2) {
            tail = prev;
        }

        prev.next = next;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        // for GC
        x = null;

        return true;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        Node<T> prev = tail;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }

        // if linked is empty
        if (x == null) {
            return null;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (index == 0) {
            head = next;
        }

        // if delete node is tail
        if (index == size - 1) {
            tail = prev;
        }

        prev.next = next;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        return x.element;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        Node<T> oldNode = node(index);
        T oldElement = oldNode.element;
        oldNode.element = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        return node(index).element;
    }

    /**
     * clear list element
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        if (head == null) {
            return false;
        }
        Node<T> x = head;
        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                return true;
            }
            if (element != null && element.equals(x.element)) {
                return true;
            }
            x = x.next;
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param <T>
     */
    private class Node<T> {

        private T element;
        private Node<T> next;

        public Node(T element, Node<T> next) {
            this.element = element;
            this.next = next;
        }
    }
}
源代码

双向循环链表

双向循环链表相比单向循环链表，降低了查找前驱节点的复杂度，时间复杂度为O(1).

同样第一次添加元素时，head与tail为同一元素，需要自指向。

package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Doubly circular linked list
 *
 * @author https://wangwei.one
 * @date 2018/12/21
 */
public class DoublyCircularLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size;
    /**
     * head node
     */
    private Node<T> head;
    /**
     * tail node
     */
    private Node<T> tail;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(index, element);
        }
    }

    /**
     * Add last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        Node<T> last = tail;
        Node<T> newNode = new Node<>(element, last, head);
        tail = newNode;
        // add element at first
        if (last == null) {
            head = newNode;
            tail.next = head;
        } else {
            last.next = newNode;
        }
        head.prev = tail;
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param index
     * @param element
     * @return
     */
    private boolean addBefore(int index, T element) {
        Node<T> target = node(index);
        Node<T> prev = target.prev;
        Node<T> newNode = new Node<>(element, prev, target);

        prev.next = newNode;
        target.prev = newNode;

        if (index == 0) {
            head = newNode;
        }

        size++;
        return true;
    }

    /**
     * remove element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        // start with head
        Node<T> x = head;
        // start with index -1
        int prevIndex = -1;

        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                break;
            }
            if (element != null && element.equals(x.element)) {
                break;
            }
            x = x.next;
            prevIndex = i;
        }

        // if this linked list is empty
        if (x == null) {
            return false;
        }

        // if don't match element
        if (prevIndex == size - 1) {
            return false;
        }

        Node<T> prev = x.prev;
        Node<T> next = x.next;

        // if delete node is head
        if (prevIndex == -1) {
            head = next;
        }

        // if delete node is tail
        if (prevIndex == size - 2) {
            tail = prev;
        }

        prev.next = next;
        next.prev = prev;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        // for GC
        x = null;

        return true;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        // if linked is empty
        if (x == null) {
            return null;
        }

        Node<T> prev = x.prev;
        Node<T> next = x.next;

        // if delete node is head
        if (index == 0) {
            head = next;
        }

        // if delete node is tail
        if (index == size - 1) {
            tail = prev;
        }

        prev.next = next;
        next.prev = prev;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        return x.element;
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return old element
     */
    @Override
    public T set(int index, T element) {
        Node<T> oldNode = node(index);
        T oldElement = oldNode.element;
        oldNode.element = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        return node(index).element;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        if (index < (size >> 1)) {
            Node<T> x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<T> x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     * @return
     */
    @Override
    public boolean contains(T element) {
        if (head == null) {
            return false;
        }
        Node<T> x = head;
        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                return true;
            }
            if (element != null && element.equals(x.element)) {
                return true;
            }
            x = x.next;
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param <T>
     */
    private class Node<T> {
        private T element;
        private Node<T> prev;
        private Node<T> next;

        public Node(T element, Node<T> prev, Node<T> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }

}
源代码

ArrayList vs LinkedList

ArrayListLinkedList
插入&
删除		O(n)O(1)
随机访问O(1)O(n)
优点连续的内存空间，可以借助CPU的预取机制内存不连续，天然支持动态扩容
缺点无法存储大数据，数组扩容耗性能频繁地插入删除操作，会导致内存碎片的增加，导致频繁的GC

参考资料

链表 算法与数据结构 数据结构 segmentfault

ifwinds

ifwinds

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

C#数据结构与算法（六）：链表——双链表（Double-LinkedList）

对于单向链表的删除，我们首先要找到单向链表待删除节点的前一个节点，然后前一个节点的下一个节点指向删除节点的后一个节点。//如果temp.Next为null就表示temp为最后一个节点；

OldBowl 2020-06-16

数据结构与算法-线性表和散列表的总结

将元素映射为下标，然后将数据存储在数组中对应下标的位置，当需要对元素进行操作时，使用同样的方法将元素映射为下标，找到下标的位置，从对应数组下标的位置取数据

ustbfym 2020-06-04

数据结构与算法（线性表）

线性表是一种最简单的线性结构。用一组地址任意的存储单元存放线性表中的数据元素。在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

freedomfanye 2020-05-03

详解Redis数据结构之跳跃表

我们先不谈Redis，来看一下跳表。还要支持输入道具名称的精确查询和不输入名称的全量查询。拍卖行商品列表是线性的，最容易表达线性结构的是数组和链表。每个元素均关联一个double类型的score，Redis 根据score进行从小到大排序；这个是 Redi

koushr 2020-11-12

Java实现单链表、栈、队列三种数据结构

它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、HashMap等等的底层都是用链表实现的。添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将

范范 2020-10-28

python的链表基础知识点

python中的链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。链表有两种类型：单链表和双链表。一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中，相反，你可以通过一个节点指向另外一个

qiangde 2020-09-13

图解！24张图彻底弄懂九大常见数据结构！ 原创 Amazing10 业余码农 5月24日

数据结构想必大家都不会陌生，对于一个成熟的程序员而言，熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合，特殊的结构在不同的应用场景中往往会带来不一样的处理效率。常用的数据结构可根据数据访问的特点分为线性结

范范 2020-07-30

数据结构 &amp; Java中的内存

顺序表 ，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。链表 ，将元素存放在通过链接构造起来的一系列存储块中。ArrayList 的 本质是对 数组Object[ ] 的封装，将该数组作为它的一个属性。对 ArrayLis

mingyunxiaohai 2020-07-19

C语言有了\"链表\"还用\"数组\"干嘛?被问懵了......

本文主要跟大家分享一下数组和链表两种内存组织类型的异同，帮助大家正确理解好这两种数据结构并合理应用。在含有Cache的系统中，由于CPU的访问速度相对普通内存而言不在一个数量等级，为了不拖累CPU都会在其中间通过Cache来作为一个缓冲，可以大大提高CPU

zhaochen00 2020-10-13

十分钟带你理解C语言中的链表

首先，指针计算机中的所有内容都是数字。在C语言中创建变量时，编译器仅按地址处理它，但是在您的代码中，您可以通过两种方式访问它：按值和按地址。堆是由编译器与您的代码链接的启动代码分配的内存块。为简化起见，假设变量Times 结束于内存位置256。最后，跳过会

Mars的自语 2020-09-27

手写最简单的LRU算法

LRU最近最少使用，它的核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。因此 LRU 算法会根据数据的历史访问记录来进行排序，如果空间不足，就会淘汰掉最近最少使用的数据。由于 LRU 算法会将最近使用的数据优先级上升，因此需要数据结构支持

steeven 2020-09-18

python/golang实现循环链表的示例代码

循环链表就是将单链表的末尾指向其头部，形成一个环。只是增加时，需要考虑空链表增加第一个节点的特殊情况；删除时需考虑删除节点是头/尾节点，和链表中只有一个节点的特殊情况。for i := 0; i < c.lenth; i++ {. if cur ==

kka 2020-09-14

PHP+Redis链表解决高并发下商品超卖问题(实现原理及步骤)

上一篇文章聊了一下使用Redis事务来解决高并发商品超卖问题，今天我们来聊一下使用Redis链表来解决高并发商品超卖问题。使用redis链表来做，因为pop操作是原子的，即使有很多用户同时到达，也是依次执行，推荐使用。trigger_error('Redi

聚沙成塔积水成渊 2020-08-16

LeetCode——合并K个排序链表

* Definition for singly-linked list.* int val;* ListNode *next;* };ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

earthhouge 2020-08-15

拿到腾讯字节快手offer后，他的LeetCode刷题经验GitHub获1300星

今天，你刷LeetCode了吗？最近，GitHub上这样一套LeetCode笔记火了。一位Java研发工程师分享了一个名为「LeetCode题目分类与面试问题整理」，一时间获得1300星。这篇笔记的作者叫袁广鑫，面试三十多家互联网公司亲历整理，曾拿到字节、

aanndd 2020-08-12

Redis知识点

　　　　　　数据都在内存中，支持持久化，主要用作备份恢复 除了支持简单的key-value模式，还支持多种数据结构的存储，比如 　　　　　　list、set、hash、zset等。　　　　　　支持二进制数据及大型对象 可以根据数据的特点替代RDBMS ，成

bluetears 2020-07-28

LRU算法list链表实现

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值

horizonheart 2020-07-19

MySQL 源码链表的实现

MySQL源码关于链表的实现在ut0lst.h文件中，其设计思路与常规略有不同，基本思想是指针嵌于对象之内，如下图所示。在这种实现方式下，构造一个链表需要同时指定对象类型和对象内指针节点的地址。我们对比一下C++11标准库中list的实现，发现其就是一个模

liushall 2020-07-18

MySQL索引原理

　　1.B+树的叶子节点包含了所有的数据；　　2.叶子节点可以直接访问其他叶子节点，不需要回到根节点；　　操作系统中，默认的是每一页是4KB；而InnoDB存储引擎，默认每一页是16KB；　　UserRecord（行记录）区域，保存的是真正的数据，会包含多

bluetears 2020-07-05

昨天，我彻底搞懂了Netty内存分配策略！

Netty 作为一款高性能的 RPC 框架必然涉及到频繁的内存分配销毁操作。基于此，在堆外内存使用方面，Netty 自己实现了一套创建、回收堆外内存池的相关功能。这些划分在 Netty 中的实现接口分别如下。另外 Netty 并不是直接对外暴露这些 AP

fengshantao 2020-07-02
ifwinds

ifwinds

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号