JAVA实现带虚拟头结点(dummyHead)的单链表.

package com.coderman.linkedlist;

/**
 * @Author zhangyukang
 * @Date 2020/8/20 12:02
 * @Version 1.0
 **/
public class LinkedList<E> {

    private class Node {
        public E element;
        public Node next;

        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }

        public Node() {
            this(null, null);
        }

        public Node(E element) {
            this(element, null);
        }
    }

    private Node dummyHead;//虚拟头结点(不保存实际的数据)

    private int size;

    public LinkedList() {
        this.dummyHead = new Node(null, null);
        this.size = 0;
    }

    //头部添加节点
    public void addFirst(E element) {
        add(element,0);
    }
    //向尾部添加一个结点
    public void addLast(E element){
        add(element,size);
    }

    //指定位置添加节点
    public void add(E element, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("传入的参数不合法");
        }
        Node preNode = dummyHead;//表示要添加的前一个节点
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        preNode.next = new Node(element, preNode.next);
        size++;
    }
    //删除指定位置的结点
    public Node remove(int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("传入的参数不合法");
        }
        Node preNode = dummyHead;//表示要添加的前一个节点
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        Node deleteNode=preNode.next;
        preNode.next=deleteNode.next;
        size--;
        return deleteNode;
    }
    //删除第一个结点
    public Node removeFirst(){
        return remove(1);
    }
    //删除最后一个结点
    public Node removeLast(){
        return remove(size-1);
    }
    //获取指定位置的结点的值
    public E get(int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("传入的参数不合法");
        }
        Node cur=dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur=cur.next;
        }
        return cur.element;
    }
    //给指定位置的结点赋值
    public void set(E element,int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("传入的参数不合法");
        }
        Node cur=dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur=cur.next;
        }
        cur.element=element;
    }

    @Override
    public String toString() {
        Node temp = dummyHead.next;
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(temp.element).append("-->");
            temp = temp.next;
        }
        stringBuilder.append("NULL");
        stringBuilder.append("]").append("\tsize=").append(this.size);
        return stringBuilder.toString();
    }
}

package com.coderman.linkedlist;


/**
 * @Author zhangyukang
 * @Date 2020/8/20 12:12
 * @Version 1.0
 **/
public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1, 0);
        list.add(2, 1);
        list.add(3, 2);
        list.add(4, 1);
        list.addFirst(100);
        System.out.println(list);
        list.remove(0);
        System.out.println(list);
        list.removeLast();
        System.out.println(list);
        Integer integer = list.get(2);
        System.out.println("value="+integer);
        list.set(10000,2);
        System.out.println(list);
    }
}

[100-->1-->4-->2-->3-->NULL]	size=5
[1-->4-->2-->3-->NULL]	size=4
[1-->4-->2-->NULL]	size=3
value=2
[1-->4-->10000-->NULL]	size=3
# 算法   数据结构  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×