Java实现线性表的链式存储(单链表)

发布于 2021-07-17  51 次阅读


坐标从1开始;和之前的数组(从0开始)不一样(也可以改);

LinkList1实现Iterable接口,需要重写iterator方法,返回实现Iterator接口并重写hasNext和next方法;

用匿名内部类返回;

    @Override
    public Iterator<T> iterator() {

        return new Iterator() {
            private Node p = head;

            @Override
            public boolean hasNext() {
                return p.next != null;
            }

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

        };
    }

单链表类如下,Node节点类是LinkList1的子类

package com.apesblog.LinkList1;

import java.util.Iterator;

public class LinkList1<T> implements Iterable<T> {
    private Node head;
    private int N;

    private class Node {
        private T item;
        private Node next;

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

    public LinkList1() {
        this.head = new Node(null, null);
        N = 0;
    }

    public T get(int i) {
        if (i < 1 || i > N) {
            throw new RuntimeException("查询位置不正确");
        }
        Node p = head;
        for (int index = 1; index <= i; index++) {
            p = p.next;
        }
        return p.item;
    }

    public void add(T t) {
        Node p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(t, null);
        N++;
    }

    public void insert(int i, T t) {
        if (i < 1 || i >= N) {
            throw new RuntimeException("插入位置不正确");
        }
        Node p = head;
        for (int index = 1; index < i; index++) {
            p = p.next;
        }
        p.next = new Node(t, p.next);
        N++;
    }

    public void delete(int i) {
        if (i < 1 || i > N) {
            throw new RuntimeException("删除位置不正确");
        }
        Node p = head;
        for (int index = 1; index < i; index++) {
            p = p.next;
        }
        p.next = p.next.next;
        N--;
    }

    @Override
    public Iterator<T> iterator() {

        return new Iterator() {
            private Node p = head;

            @Override
            public boolean hasNext() {
                return p.next != null;
            }

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

        };
    }

}

测试代码如下:

package com.apesblog.LinkList1;

public class Test {

    public static void main(String[] args) {
        LinkList1<String> l = new LinkList1<String>();
        l.add("1");
        l.add("2");
        l.add("3");
        l.add("5");
        l.add("6");
        System.out.println("获取第2个元素:" + l.get(2));

        StringBuilder str = new StringBuilder(300);
        str.append("遍历:");
        for (String s : l) {
            str.append(s + " ");
        }
        System.out.println(str);

        l.insert(4, "4");
        str.delete(0, str.length());
        str.append("插入:");
        for (String s : l) {
            str.append(s + " ");
        }
        System.out.println(str);

        str.delete(0, str.length());
        l.delete(1);
        str.append("删除:");
        for (String s : l) {
            str.append(s + " ");
        }
        System.out.println(str);
    }

}

结果: