单项链表

单项链表实现

image.png

package com.test.compare.list;

import java.util.Iterator;

public class LinkList<T> implements Iterable<T>{
    private Node head;// 记录头节点
    private int N; // 记录数组长度
    
    private class Node {
        T item; // 存储数据
        Node next; // 存储下一个节点
        
        public Node(T item, LinkList<T>.Node next) {
            super();
            this.item = item;
            this.next = next;
        }
    }

    public LinkList() {
        // 1. 初始化头结点
        this.head = new Node(null, null);
        // 2. 初始化元素个数
        this.N = 0;
    }
    
    // 清空链表
    public void clear() {
        this.head.next = null;
        this.N = 0;
    }
    
    // 获取链表长度
    public int length() {
        return N;
    }
    
    // 判断链表是否为空
    public boolean isEmpty() {
        
        return N == 0;
    }
    
    // 获取指定位置i的元素
    public T get(int i) {
        // 通过循环，从头结点开始，往后找i次就能找到对应的元素
        Node node = head.next;
        for(int index=0; index<i; index++) {
            node = node.next;
        }
        return node.item;
    }
    
    // 向链表中插入元素
    public void insert(T t) {
        // 找到当前连接的最后一个结点
        Node node = this.head;
        while(node.next != null) {
            node = node.next;
        }
        // 创建新结点，保存t
        Node newNode = new Node(t, null);
        // 让最后一个结点指向新结点
        node.next = newNode;
        // 元素个数+1
        N++;
    }
    
    // 向链表中指定位置i插入元素
    public void insert(T t, int i) {
        // 1. 找到i位置的前一个结点
        Node pre = this.head;
        for(int index=0; index<i-1; index++) {
            pre = pre.next;
        }
        // 2. 找到i位置的结点
        Node iNode = pre.next;
        // 3. 创建新结点，并且新结点需要指向原来位置的结点，让i位置的前一个结点指向新节点
        Node newNode = new Node(t, null);
        pre.next = newNode;
        newNode.next = iNode;
        // 元素个数+1
        N++;
    }
    
    // 删除指定位置i的元素，并返回被删除的元素
    public T remove(int i) {
        // 1. 找到 i位置的前一个结点
        Node pre = this.head;
        for(int index=0; index<i-1; index++) {
            pre = pre.next;
        }
        // 2. 找到i位置的结点
        Node iNode = pre.next;
        // 3. 找到i位置的下一个结点
        Node iNextNode = iNode.next;
        // 4. 让i位置的前一个结点，指向i位置的下一个几点
        pre.next = iNextNode;
        // 元素个数-1
        N--;
        return iNode.item;
    }
    
    // 查找指定元素t在链表中首次出现的位置
    public int index(T t) {
        // 从头结点开始，依次遍历每一个结点，取出item和t比较
        Node 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<T> 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;
        }
    }
    
    public static void main(String[] args) {
        LinkList<String> lk= new LinkList<>();
        lk.insert("张三");
        lk.insert("李四");
        lk.insert("王五");
        lk.insert("赵六");
        lk.insert("王麻子",3);
        
        for (String value : lk) {
            System.out.println(value);
        }
        System.out.println("=====================");
        String removeStr = lk.remove(4);
        System.out.println("removestr:"+removeStr);
        lk.clear();
        System.out.println(lk.length());
    }
}

单链表反转

反转前：1->2->3->4
反转后：4->3->2->1