数据结构之线性表的链式储存及单链表实现

1. 什么是线性表

1. 线性表是最常用，最简单，也是一种最基本的数据结构。
   

   
   

2. 线性表在计算机中可以使用顺序储存与链式储存两种存储结构来实现。
   

   
   

顺序表：顺序存储结构表示的线性表为顺序表
链表：链表是采用链式存储结构实现的，其中链表又有单链表，双向链表，循环链表之分。

2. 顺序表的局限

1. 若要为顺序表扩容，则需要分配一个地址连续且更大的存储空间，并把原来所有的数据元素一并拷贝到新的存储空间中。
   

   
   

   如果数据量大则会非常耗时

2. 因为顺序表要求逻辑上相邻的元素物理地址必须是相邻的，这就使得增删数据元素会引起一半的数据元素移动。
   

   
   

顺序表适用于“静态”线性表，即线性表形成后，就很少进行插入与删除操作。

对于需要频繁执行插入与删除操作的”动态“线性表，通常采用链式存储结构。

3. 什么是链表

链式存储方式不需要逻辑上相邻的元素在物理上也相邻，它是一组地址任意的存储单元来存放数据元素的值。

因此，链式存储结构没有顺序结构存储的局限性，但却失去了可随机读写的特点，在链式存储上只能顺序读取。

4. 单链表

采用链式存储结构的线性表称为链表，链表的每个节点存放数据元素的数据和存放指向逻辑上相邻节点的指针。

若一个节点中只包含一个指针，则该链表被称为单链表。

5. 单链表概念图

1. 头指针：第一个元素的存储地址
2. 头节点：为了操作方便，头节点不存放数据，指针指向第一个节点
3. 首节点：第一个节点
4. 尾节点：链表中最后的一个节点
   
   

6. 单链表实现 6.1 节点类

由于链表是由多个节点连接组成的。

因此需要先设计节点类

// setter getter ... 略
public class Node<T> {
    private T data;
    private Node<T> next;
}

6.2 链表

为了规范，习惯性定义一个接口并实现

public interface IList<T> {
    void add(T value);

    void remove(int i);

    T get(int i);

    void insert(int i, T value);

    int indexOf(T value);

    int length();

    void clear();

    boolean isEmpty();
}

6.3 实现链表

public class LinkList<T> implements IList<T> {

    private Node<T> headNode;

    private Node<T> lastNode;

    private int length;

    public LinkList() {
        this.headNode = new Node<>();
        this.lastNode = this.headNode;
    }

    @Override
    public void add(T value) {
        Node<T> nextNode = new Node<>(value);
        lastNode.setNext(nextNode);
        this.lastNode = nextNode;
        this.length++;
    }

    @Override
    public void remove(int i) {
        if (i < 0 || i >= this.length) {
            throw new IndexOutOfBoundsException();
        }

        int count = 0;
        Node<T> parent = this.headNode;
        while (count++ < i) {
            parent = parent.getNext();
        }
        parent.setNext(parent.getNext().getNext());

        this.length--;
    }

    @Override
    public T get(int i) {
        if (i < 0 || i >= this.length) {
            throw new IndexOutOfBoundsException();
        }
        int count = 0;
        Node<T> tmp = this.headNode;
        while ((tmp = tmp.getNext()) != null && count++ < i) ;
        return tmp.getData();
    }

    @Override
    public void insert(int i, T value) {
        if (i < 0 || i >= this.length) {
            throw new IndexOutOfBoundsException();
        }

        Node<T> node = new Node<>(value);

        Node<T> tmp = this.headNode;
        for (int j = 0; j < i; j++) {
            tmp = tmp.getNext();
        }
        node.setNext(tmp.getNext());
        tmp.setNext(node);

        this.length++;
    }

    @Override
    public int indexOf(T value) {
        Node<T> tmp = this.headNode;
        int index = -1;
        while ((tmp = tmp.getNext()) != null) {
            if (tmp.getData().equals(value)) {
                return ++index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public int length() {
        return this.length;
    }

    @Override
    public void clear() {
        this.headNode = new Node<>();
        this.lastNode = this.headNode;
        this.length = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.length == 0;
    }
}

6.4 测试链表

测试依赖：junit

public class LinkListTest {

    private final LinkList<Integer> linkList = new LinkList<>();

    @Before
    public void fill() {
        linkList.add(1);
        linkList.add(2);
        linkList.add(3);
        linkList.add(4);
        linkList.add(5);
    }

    @After
    public void show() {
        for (int i = 0; i < linkList.length(); i++) {
            System.out.printf("i = %d value = %s %n", i, linkList.get(i));
        }
    }

    @Test
    public void remove() {
        linkList.remove(0);
        linkList.remove(1);
    }

    @Test
    public void get() {
        System.out.println(linkList.get(1));
    }

    @Test
    public void isEmpty() {
        System.out.println(linkList.isEmpty());
    }

    @Test
    public void indexOf() {
        System.out.println(linkList.indexOf(2));
    }

    @Test
    public void insert() {
        linkList.insert(1, 99);
        linkList.insert(0, 100);
    }

    @Test
    public void clear() {
        linkList.clear();
    }

    @Test
    public void length() {
        System.out.println(linkList.length());
    }
}