（四）线性表 ---→ 链表 ---→ 单链表-蒲公英云

文章目录

- 概念
- 特点
- 复杂度
- `java` 代码实现

概念

摘抄自维基百科

链表中最简单的一种是单向链表，它包含两个域，一个 信息域 和一个 指针域 。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

在这里插入图片描述

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

单链表是链表最基本的结构 。

一般在在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。

特点

单向链表（又名单链表、线性链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。

复杂度

插入、删除，复杂度都是 O(1) 级别
存、取的复杂度都是 0(n) 级别

`java` 代码实现

/* * listEmpty() 判断线性表是否为空，为空返回 true ，否则返回 false * clearList()将线性表清空，置为空表 * getElem(index)返回线性表中的第 index+1 元素 * setElem(index,elem) 设置线性表中角标为 index 的元素为 elem * getElemIndex(elem) 返回线性表中元素 elem 的下标 index ，返回 -1 代表线性表中没有该元素。 * insertElem(int index,elem) 在线性表的 index 下标处，插入元素 elem * delete(index) 删除并返回线性表中下标为 index 的元素 * length() 返回线性表的长度 * size() 返回线性表中元素的个数 */
/** * @author yiaz * @date 2019/7/15 * @description 单链表 */
public class SingleLinkedList<E> { 
    /** * 是否是插入 */
    private static final boolean IS_INSERT = true;
    private int length;
    private Node head;
    /** * 链表节点 */
    private class Node { 
        E elem;
        Node next;
        public Node() { 
            elem = null;
            next = null;
        }
    }
    public SingleLinkedList() { 
        // 初始化头结点
        head = new Node();
        length = 0;
    }
    public boolean listEmpty() { 
        return length == 0;
    }
    public void clearList() { 
        length = 0;
        head.next = null;
    }
    /** * getElem(index)返回线性表中的第 index+1 元素 */
    public E getElem(int index) { 
        Node temp = head;
        for (int i = 0; i <= index; i++) { 
            temp = temp.next;
        }
        return temp.elem;
    }
    /** * setElem(index,elem) 设置线性表中角标为 index 的元素为 elem */
    public E setElem(int index, E elem) { 
        boolean flag = validateIndex(index, !IS_INSERT);
        if (!flag) { 
            throw new RuntimeException("下标越界");
        }
        Node temp = head;
        for (int i = 0; i <= index; i++) { 
            temp = temp.next;
        }
        E originalValue = temp.elem;
        temp.elem = elem;
        return originalValue;
    }
    /** * getElemIndex(elem) 返回线性表中元素 elem 的下标 index ，返回 -1 代表线性表中没有该元素。 */
    public int getElemIndex(E elem) { 
        Node temp = head;
        int index = 0;
        while (temp.next != null) { 
            temp = temp.next;
            if (temp.elem.equals(elem)) { 
                return index;
            }
            index++;
        }
        return -1;
    }
    /** * insertElem(int index,elem) 在线性表的 index 下标处，插入元素 elem */
    public void insertElem(int index, E elem) { 
        boolean flag = validateIndex(index, IS_INSERT);
        if (!flag) { 
            throw new RuntimeException("角标越界");
        }
        if (elem == null) { 
            throw new RuntimeException("不可以插入 null 对象");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) { 
            temp = temp.next;
        }
        Node node = new Node();
        node.elem = elem;
        node.next = temp.next;
        temp.next = node;
        length++;
    }
    /** * delete(index) 删除并返回线性表中下标为 index 的元素 */
    public E delete(int index) { 
        boolean flag = validateIndex(index, !IS_INSERT);
        Node temp = head;
        for (int i = 0; i < index; i++) { 
            temp = temp.next;
        }
        E elem = temp.next.elem;
        temp.next = temp.next.next;
        length--;
        return elem;
    }
    /** * length() 返回线性表的长度 */
    public int getLength() { 
        return length;
    }
    /** * 验证 index 是否合法 * * @param index 角标 * @param flag true 表示插入、false 表示 删除、查询、更新 * @return true 代表 校验通过 */
    private boolean validateIndex(int index, boolean flag) { 
        if (flag) { 
            if (!(index >= 0 && index <= length)) { 
                return false;
            }
        } else { 
            if (!(index >= 0 && index < length)) { 
                return false;
            }
        }
        return true;
    }
}

Junit 测试代码

import org.junit.Before;
import org.junit.Test;
import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;
/** * @author yiaz * @date 2019/7/16 * @description */
public class SingleLinkedListTest { 
    private SingleLinkedList<String> list;
    @Before
    public void setUp() throws Exception { 
        // 初始化单链表
        list = new SingleLinkedList<>();
    }
    @Test
    public void listEmpty() throws Exception { 
        assertThat(true, is(list.listEmpty()));
        list.insertElem(0, "first");
        assertThat(false, is(list.listEmpty()));
    }
    @Test
    public void clearList() throws Exception { 
        list.insertElem(0, "first");
        assertThat(false, is(list.listEmpty()));
        list.clearList();
        assertThat(0, is(list.getLength()));
    }
    @Test
    public void getElem() throws Exception { 
        list.insertElem(0, "first");
        list.insertElem(1, "secend");
        list.insertElem(2, "third");
        assertThat("secend", is(list.getElem(1)));
    }
    @Test(expected = RuntimeException.class)
    public void setElem() throws Exception { 
        list.insertElem(0, "first");
        assertThat("first", is(list.getElem(0)));
        list.setElem(2, "sasa");
        list.setElem(0, "sasa");
        assertThat("sasa", is(list.getElem(0)));
    }
    @Test
    public void getElemIndex() throws Exception { 
        list.insertElem(0, "first");
        list.insertElem(1, "1");
        list.insertElem(2, "2");
        assertThat(-1, is(list.getElemIndex("yiaz")));
        assertThat(0, is(list.getElemIndex("first")));
        assertThat(2, is(list.getElemIndex("2")));
        assertThat(1, is(list.getElemIndex("1")));
    }
    @Test(expected = RuntimeException.class)
    public void insertElem() throws Exception { 
        assertThat(true, is(list.listEmpty()));
        list.insertElem(2, "haha");
        list.insertElem(0, "haha");
        assertThat(false, is(list.listEmpty()));
    }
    @Test
    public void delete() throws Exception { 
        list.insertElem(0, "first");
        list.insertElem(1, "1");
        list.insertElem(2, "2");
        assertThat(3, is(list.getLength()));
        assertThat("1", is(list.delete(1)));
        assertThat("2", is(list.delete(1)));
        assertThat(1, is(list.getLength()));
    }
    @Test
    public void length() throws Exception { 
        assertThat(0, is(list.getLength()));
        list.insertElem(0, "first");
        assertThat(1, is(list.getLength()));
        list.insertElem(1, "1");
        list.insertElem(2, "2");
        assertThat(3, is(list.getLength()));
    }
}