线性表之 链表

  上节分析了顺序表,这次我们分析一下链表,并简单手写一个单链表.

  顺序表的特征上一节已经讲过:尾插效率高,支持随机访问;中间插入或删除效率低.

  那么链式表又是怎样一种结构呢?他的存储又是怎么样的?

  如果说顺序表是一个萝卜一个坑,那么链式表整体的结构就像一条链子.

  如图所示:

image.png

  在链表中,每一个元素都被看做是一个节点,他的数据结构底层是个Object 有一个属性next指向下一个元素,另一个属性用于存储数据.

知道了链表的数据结构,我们就来实现一下简单的单链表,包括常用的以下几个方法:

  1. add系列方法

  2. remove系列方法

  3. get系列方法

  4. Set方法

  5. 转置方法

  首先,按照数据结构,创建一个静态内部类 Node<E>,包含两个属性,E 和 Node<E>.其中E表示数据类型,Node<E>表示下一个节点.

 private static class Node<E> {

        E item;

        Node<E> next;

        Node(E element, Node<E> next) {

            this.item = element;

            this.next = next;

        }

}

Add系列方法:

  add(E e)向末尾添加元素:

 public void add(E e) {

        if (head == null) {

            //首次添加

            head = new Node(e);

            head.next = null;

            size++;

        } else {

            Node node = head;

            Node<E> node1 = new Node<>(e);

            while (node.next != null) {

                node = node.next;

            }

            node.next = node1;

            size++;

        }

    }

  add(int location,E e)向指定位置添加元素:

 public void add(int location, E e) {

        if (location > size) {

            throw new IndexOutOfBoundsException("index out of bounds");

        }

        Node node1 = new Node(e);

        if (location == 0) {

            node1.next = head;

            head = node1;

        } else {

            int now = 0;

            Node node = head;

            while (now != location-1) {

                now++;

                node = node.next;

            }

            Node node2 = node.next;

            node.next = node1;

            node1.next = node2;

        }

        size++;

    }

remove方法:

  E remove(int location),删除对应位置元素,并返回元素的值:

 public E remove(int location) {

        if (location < 0 || location >= size) {

            throw new IndexOutOfBoundsException("index out if bounds");

        }

        size--;

        if (location == 0) {

            E item = head.item;

            head = head.next;

            return item;

        } else {

            Node<E> prev = head;

            int now = 0;

            while (now != location-1) {

                prev = prev.next;

                now++;

            }

            Node<E> next = prev.next;

            Node<E> next1 = next.next;

            prev.next = next1;

            return next.item;

        }

    }

get方法:

  E get(int location),获取对应位置节点的数据:

public E get(int location) {
    if (location < 0 || location >= size) {
        throw new IndexOutOfBoundsException("index out if bounds");
    }
    Node<E> e = head;
    int now = 0;
    while (now != location) {
        e = e.next;
        now++;
    }
    return e.item;
}

set方法:
  set(int location, E e),修改对应位置的节点数据:

  public void set(int location, E e) {
        if (location < 0 || location >= size) {
            throw new IndexOutOfBoundsException("index out if bounds");
        }
        int now = 0;
        Node node = head;
        while (now != location) {
            node = node.next;
            now++;
        }
        node.item = e;
    }

转置:

  1. 循环转置

public void reverse() {
    if (size <=1) {
        return;
    }
    Node prev = head;
    Node curr = head.next;
    Node temp;
    while (curr != null) {
        temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    head.next = null;
    head = prev;
}

  2. 递归转置

public void reverse2() {
    if (size <=1) {
        return;
    }
    reverse2(head);
}

public void reverse2(Node head) {
    if(head==null||head.next==null) {
        this.head=head;
        return;
    }
    reverse2(head.next);
    head.next.next=head;
    head.next=null;
}

关于转置这块的解释,可以参见我的另一篇文章: 数据结构之List(一) 手写单链表

下节我们回顾一下栈和队列.