2009_线性表之链表之单向链表

之前我们已经使用顺序结构实现了线性表, 我们会发一虽然顺序表的查询很快,时间复杂度为O(1)但是增删的效率是比较低的, 因为每一次增删操作都 伴着大量的数据元素移动. 这个问题 有没有解决方案呢? 有, 我们可以使用另外一种存储结构实现线性表, 链式存储结构.

链表是一种物理存储单元上非连续,非顺序拵 储结构,其物理结构不能直观的表示数元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接序决定的. 链表由一系列结点组成,结点可以运行时动态生成.

2.2.1 单向链表

单向链表是链表的一种, 它由多个结点组成,每个结点者由一个数据域和一个指针域组成, 数据用来存储数据,指针域用来指向其后继结点.链表的头结点的数据域不存储数据, 指针域指向第一个真正存储数据的结点.

2.2.1.1 API设计

2.2.1.2 代码实现

package b_linear.b_linkedlist;

import java.util.Iterator;

/**
 * 单向链表
 */
public class LinkList<T> implements Iterable {
    //成员变量
    private Node head;
    private int n;



    //成员内部类
    private class Node<T> {
        //成员变量: 存储元素
        public T item;
        //下一个结点
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //构造器
    public LinkList() {
        //初始化头结点
        this.head = new Node(null, null);
        //初始化元素个数
        this.n = 0;
    }

    //成员方法
    //清空
    public void clear() {
        head.next = null;
        this.n = 0;
    }

    //获取长度,即元素个数
    public int length() {

        return this.n;
    }

    //是否为空
    public boolean isEmpty() {

        return this.n == 0;
    }

    //获取元素
    public T get(int i) {
        //通过循环, 从头结点开始往后, 依次找到i位置
        Node<T> node = head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.item;
    }

    //添加元素
    public void insert(T t) {
        //找到最后一个结点
        Node<T> node = head;
        while (node.next != null) {
            node = node.next;
        }
        //创建新结点保存元素
        Node<T> newNode = new Node<>(t, null);

        //最后一个结点指向新结点
        node.next = newNode;
        //元素个数+1
        this.n++;
    }

    //指定位置添加元素
    public void insert(int i, T t) {
        //找到i位置前一个结点
        Node<T>  pre = head;
        for (int index = 0; index <= i-1; index++) {
            pre= pre.next;
        }
        //找到i位置的结点
        Node<T> curr = pre.next;
        //创建新结点, 新结点指向原来i位置的结点
        Node<T> newNode = new Node<>(t, curr);
        //原来i位置前一个节点, 指向新节点
        pre.next = newNode;
        //元素加1
        this.n++;
    }

    //删除i位置处的元素
    public T remove(int i) {
        //找到i前一个位置的结点
        Node<T>  pre = head;
        for (int index = 0; index <= i-1; index++) {
            pre= pre.next;
        }
        //找到i位置的结节
        Node<T> curr = pre.next;
        //找到i位置下一个结点
        Node<T> nextNode = curr.next;
        //前一个节点指向下一个结点
        pre.next = nextNode;

        //元素个数一1
        this.n--;
        return curr.item;
    }

    //查找元素首次出现位置
    public int indexOf(T t) {
        //从头结点开始, 依次找出每一个结点, 取出item与t比较, 如果相迥找到了
        Node<T> node = head;
        for (int i = 0; node.next!=null; i++) {
            node = node.next;
            if(node.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator {
        private Node node;
        public LIterator(){
            this.node = head;
        }
        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        @Override
        public Object next() {
            node = node.next;
            return node.item;
        }
    }

}

2.2.1.3 测试

package b_linear.b_linkedlist;

import b_linear.a_sequencelist.SquenceList;

/**
 * 顺序表测试
 */
public class LinkListTest {
    public static void main(String[] args) {
        //创建对象
        LinkList<String> s1 = new LinkList<>();
        //插入
        s1.insert("姚明");
        s1.insert("科比");
        s1.insert("麦迪");
        s1.insert(1, "詹姆斯");

        for(Object s : s1) {
            System.out.println((String)s);
        }
        System.out.println("-----");

        //获取
        String getResult = s1.get(1);
        System.out.println(getResult);

        //删除
        String removeResult = s1.remove(0);
        System.out.println(removeResult);

        //清空
        s1.clear();
        System.out.println("清空后的元素个数: " + s1.length());

    }
}

2009_线性表之链表之单向链表

原文：https://www.cnblogs.com/coder-Joe/p/13697772.html