Skip to main content
 首页 » 编程设计

java算法之自定义线性结构-单链表方式

2022年07月18日29cyq1162
package com.rongyi.platform.game.web.controller; 
 
import java.util.Iterator; 
 
/** 
 * @desc: 线性结构-单链表实现 
 * @author: 毛会懂 
 * @create: 2020-12-25 15:11:00 
 **/ 
public class MyLinkList<T> implements MyList<T> { 
 
    private Node head; 
    private Integer N; 
 
    //链表头是一个空节点 
    public MyLinkList(){ 
        head = new Node(null,null); 
        N = 0; 
    } 
 
    //添加元素 
    @Override 
    public void add(T t) { 
        Node temp = head; 
        while (temp.next != null){ 
            temp = temp.next; 
        } 
        temp.next = new Node(t,null); 
        N++; 
    } 
 
    //向指定位置添加元素 
    @Override 
    public void add(Integer i, T t) { 
        if(i < 0  || i > N){ 
            throw new RuntimeException("位置不正确"); 
        } 
        Node current = head; 
        for(int index = 0; index < i;index++){ 
             current = current.next; 
        } 
        Node node = new Node(t,null); 
        node.next = current.next; 
        current.next = node; 
        N++; 
    } 
 
    //移除指定位置元素 
    @Override 
    public T remove(Integer i) { 
        if(i < 0  || i >= N){ 
            throw new RuntimeException("位置不正确"); 
        } 
        Node pre = head; //上一个元素 
        for(int index = 0;index <i;index++){ 
            pre = pre.next; 
        } 
        Node delNode = pre.next; 
        pre.next = delNode.next; 
        N--; 
        return delNode.t; 
    } 
 
    //更新指定位置的元素 
    @Override 
    public void update(int i, T t) { 
        Node pre = head; //上一个元素 
        for(int index = 0;index <i;index++){ 
            pre = pre.next; 
        } 
        Node nextNode = pre.next.next; //下一个元素 
        pre.next = new Node(t,null); 
        pre.next.next = nextNode; 
    } 
 
    //得到指定位置的元素 
    @Override 
    public T get(int i) { 
        if(i < 0 || i >=N){ 
            throw new RuntimeException("位置不正确"); 
        } 
        Node cur = head; 
        for(int index = 0; index <=i;index++){ 
            cur = cur.next; 
        } 
        return cur.t; 
    } 
 
    /** 
    * 查找某一个元素的位置 
    **/ 
    @Override 
    public Integer indexOf(T t) { 
        Node cur = head; 
        for(int index = 0;index < N ;index++){ 
            cur = cur.next; 
            if(cur.t.equals(t)){ 
                return index; 
            } 
        } 
        return -1; 
    } 
 
    @Override 
    public Boolean isEmpty() { 
        return N==0; 
    } 
 
    @Override 
    public Integer length() { 
        return N; 
    } 
 
    //清除链表 
    @Override 
    public void clean() { 
        head.next = null; 
        N = 0; 
    } 
 
    @Override 
    public Iterator<T> iterator() { 
        return new MyIterator(); 
    } 
 
    //翻转链表 
    public void reverse(){ 
        if(N == 0){ 
            return; 
        } 
        //第0个节点(下标从0算) 
        reverse(head.next); 
    } 
 
    //翻转某一个节点 
    private Node reverse(Node cur){ 
        if(cur.next == null){ 
            head.next = cur; 
            return cur; 
        } 
        //当前节点的下一个节点,即为翻转后的上一个节点 
        Node pre = reverse(cur.next); 
        pre.next = cur; 
        cur.next = null; 
        return cur; 
    } 
 
    private class MyIterator implements Iterator<T>{ 
        private Node node; 
        public MyIterator(){ 
            node = head; 
        } 
        @Override 
        public boolean hasNext() { 
            return node.next != null; 
        } 
 
        @Override 
        public T next() { 
            T t = node.next.t; 
            node = node.next; 
            return t; 
        } 
 
    } 
 
    private class Node{ 
        private T t; 
        private Node next; 
 
        public Node(T t,Node node){ 
            this.t = t; 
            this.next = node; 
        } 
    } 
}

测试:

public static void main(String[] args) {
MyList<Integer> list = new MyLinkList<>();
list.add(1);
list.add(2);
list.add(2,3);
list.add(3,4);
System.out.println("--------");
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("--------");
System.out.println(list.indexOf(2)); //查找某一个元素的值
list.remove(1);
list.add(0,-1);
list.update(0,-2);
System.out.println(list.isEmpty());
System.out.println(list.length());
System.out.println(list.get(0));
//list.clean();
System.out.println(list.length());
System.out.println("----------------");
//第一种遍历方式
for (Integer i : list){
System.out.println(i);
}

System.out.println("-------------");
//第二种遍历方式
list.forEach(System.out::println);
System.out.println("--------");
//第三种遍历方式
Iterator<Integer> iterator2 = list.iterator();
while (iterator2.hasNext()) {
System.out.println(iterator2.next());
}
System.out.println("单链表翻转");
((MyLinkList)list).reverse();
//第三种遍历方式
Iterator<Integer> iterator33 = list.iterator();
while (iterator33.hasNext()) {
System.out.println(iterator33.next());
}
}

本文参考链接:https://www.cnblogs.com/maohuidong/p/14216108.html