（四）线性表 ---→ 链表 ---→ 单链表

女爷i 2021-12-10 04:05 384阅读 0赞

### 文章目录 ###

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

--------------------

## 概念 ##

> 摘抄自 维基百科

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

![在这里插入图片描述][20190715145112226.png]

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

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

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

--------------------

## 特点 ##

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

--------------------

## 复杂度 ##

1.  插入、删除，复杂度都是 `O(1)` 级别
2.  存、取 的复杂度都是 `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()));
        }
    
    }

[20190715145112226.png]: /images/20211209/bd38f0cbc1484727a3322b03ddb3f619.png