JAVA 手動(dòng)實(shí)現(xiàn)LinkedList

JAVA 手動(dòng)實(shí)現(xiàn)LinkedList

節(jié)點(diǎn)

package com.ghg.data_structure.link;

public class Node<T> {
    /**
     * 數(shù)據(jù)
     */
    public T data;
    /**
     * 前一個(gè)
     */
    public Node pre;
    /**
     * 后一個(gè)
     */
    public Node next;


    public Node() {
        super();
    }
    
    /**
     * 
     * @param data 數(shù)據(jù)
     * @param pre 前一個(gè)
     */
    public Node(T data, Node pre, Node next) {
        super();
        this.data = data;
        this.pre = pre;
        this.next = next;
    }


    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return data+" ";
    }
}

List接口

package com.ghg.data_structure.link;

public interface MyList<T> {

    /**
     * 是否為空
     * @return
     */
    public boolean isEmpty();

    /**
     * 大小
     * @return
     */
    public int size();

    /**
     * 添加到第一個(gè)
     * @param t
     * @return
     */
    public boolean addFirst(T t);

    /**
     * 獲取第一個(gè)
     * @return
     */
    public T getFirst();

    /**
     * 添加到最后
     * @param t
     * @return
     */
    public boolean addLast(T t);

    /**
     * 獲取最后一個(gè)元素
     * @return
     */
    public T getLast();

    /**
     * 添加默認(rèn)添加到最后
     * @param t
     * @return
     */
    public boolean add(T t);

    /**
     * 添加到指定位置
     * @param index 索引
     * @param t 數(shù)據(jù)
     * @return
     */
    public boolean add(int index, T t);

    /**
     * 獲取指定位置的元素
     * @param index 索引
     * @return
     */
    public T get(int index);
    
    
    /**
     * 移除指定元素
     * @param index
     * @return
     */
    public T remove(int index);
    
    /**
     * 移除第一個(gè)
     * @return
     */
    public boolean removeFirst();
    /**
     * 移除最后一個(gè)
     * @return
     */
    public boolean removeLast();
    
    /**
     * 是否包含
     * @param object
     * @return
     */
    public boolean contains(Object object);
    
    /**
     * 獲取迭代器
     * @return
     */
    public MyIterator<T> iterator();
}

迭代器接口

package com.ghg.data_structure.link;

public interface MyIterator<T> {

    public boolean hasNext();
    
    public T next();
    
    public boolean hasPrevious();  

    public T previous();
}

實(shí)現(xiàn)

package com.ghg.data_structure.link;

import java.util.NoSuchElementException;

public class MyLinkedList<T> implements MyList<T> {

    private int size = 0;

    private Node<T> first;

    private Node<T> last;

    private int position = 0;

    public MyLinkedList() {
        this.first = null;
        this.last = null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public boolean addFirst(T t) {
        Node<T> f = first;

        Node<T> newNode = new Node<T>(t, null, first);

        first = newNode;

        if (f == null) {
            last = newNode;
        } else {
            f.pre = newNode;
        }
        size++;
        return true;
    }

    public T getFirst() {
        return first.data;
    }

    public boolean addLast(T t) {

        Node<T> l = last;
        Node<T> newNode = new Node<T>(t, l, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
        return true;
    }

    public T getLast() {
        return last.data;
    }

    public boolean add(T t) {
        return addLast(t);
    }

    public boolean add(int index, T t) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
        }

        if (index == size) {
            return addLast(t);
        }

        Node<T> current = first;

        for (int i = 0; i < index; i++) {
            current = current.next;
        }

        Node<T> pre = current.pre;

        Node<T> newNode = new Node<T>(t, pre, current);

        current.pre = newNode;
        /**
         * 如果沒(méi)有前置元素說(shuō)明是第一個(gè)
         */
        if (pre == null) {
            first = newNode;
        } else {
            pre.next = newNode;
        }

        size++;
        return true;
    }

    public T get(int index) {

        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
        }

        Node<T> current = first;

        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    @Override
    public String toString() {

        Node<T> current = first;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {

            sb.append(current);
            current = current.next;
        }
        return sb.toString();

    }

    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
        }

        Node<T> current = first;

        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        /**
         * 獲取當(dāng)前元素的前置也后置元素,將這2個(gè)元素相連接
         */
        final Node<T> next = current.next;
        final Node<T> prev = current.pre;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
        }

        if (next == null) {
            last = prev;
        } else {
            next.pre = prev;
        }

        size--;
        return current.data;
    }

    /**
     * 移除第一個(gè)
     */
    public boolean removeFirst() {
        /**
         * 獲取第一個(gè)元素
         */
        Node<T> current = first;
        /**
         * 獲取第一個(gè)元素的下一個(gè)元素
         */
        Node<T> next = current.next;
        /**
         * 賦值
         */
        first = next;

        /**
         * 判斷下一個(gè)是不是空,如果為空就說(shuō)明是最后一個(gè),目前只有一個(gè)元素
         */
        if (next == null) {
            last = null;
        } else {
            // 前置設(shè)置為空,因?yàn)槭堑谝粋€(gè)了
            next.pre = null;
        }
        size--;
        return true;
    }

    /**
     * 移除最后個(gè)
     */
    public boolean removeLast() {
        /**
         * 獲取最后一個(gè)元素
         */
        Node<T> current = last;
        /**
         * 獲取最后一個(gè)的前一個(gè)元素
         */
        Node<T> pre = current.pre;
        /**
         * 賦值
         */
        last = pre;

        /**
         * 判斷前置是不是空,如果為空說(shuō)明第一個(gè)為NULL
         */
        if (pre == null) {
            first = null;
        } else {
            // 將最后一個(gè)元素的,后置設(shè)置為空
            pre.next = null;
        }

        size--;
        return true;
    }

    public boolean contains(Object object) {
        if (object == null) {
            return false;
        }
        int index = 0;
        for (Node<T> current = first; current.next != null; current = current.next) {
            if (object.equals(current.data)) {
                break;
            }
            index++;
        }
        System.out.println("contains  index:  " + index);
        return index > 0;
    }
/*
    *//**
     * 是否有更多
     *//*
    public boolean hasNext() {

        if (position < size) {
            return true;
        } else {
            position = 0;

            return false;
        }

    }

    *//**
     * 下一個(gè)元素
     *//*
    public T next() {

        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        return get(position++);
    }*/

    public class MyInnerIterator<T> implements MyIterator<T> {

        private MyLinkedList<T> myLinkedList;
        /**
         * 游標(biāo)
         */
        private int cursor = 0;

        public MyInnerIterator(MyLinkedList<T> linkedList) {
            this.myLinkedList = linkedList;
        }

        public boolean hasNext() {
            return cursor<size;
        }

        public T next() {
            return myLinkedList.get(cursor++);
        }

        public boolean hasPrevious() {
            System.out.println("cursor  "+cursor);
            return cursor>0;
        }

        public T previous() {
            return myLinkedList.get(--cursor);
        }

    }

    /**
     * 獲取迭代器
     */
    public MyIterator<T> iterator() {
        return new MyInnerIterator<T>(this);
    }

}

測(cè)試

package com.ghg.data_structure.link;

public class MyListTest1 {

    public static void main(String[] args) {

        MyLinkedList<Integer> myLinkedList = new MyLinkedList<Integer>();

        myLinkedList.addFirst(3);

        myLinkedList.addFirst(5);

        System.out.println("\n 全部: " + myLinkedList.toString());

        System.out.println("\n 獲取第一個(gè): " + myLinkedList.getFirst());
        System.out.println("\n 獲取最后一個(gè): " + myLinkedList.getLast());

        myLinkedList.addLast(9);

        myLinkedList.addLast(-1);
        System.out.println("\n 全部: " + myLinkedList.toString());
        System.out.println("\n size : " + myLinkedList.size());

        myLinkedList.addFirst(67);

        System.out.println("\n 全部: " + myLinkedList.toString());

        System.out.println("\n index : " + myLinkedList.get(1));

        myLinkedList.add(45);
        myLinkedList.add(-80);
        System.out.println("\n 全部: " + myLinkedList.toString());

        myLinkedList.add(0, 45);
        System.out.println("\n 全部: " + myLinkedList.toString());

        myLinkedList.add(8, 43);
        System.out.println("\n 全部: " + myLinkedList.toString());

        myLinkedList.add(1, 33);
        myLinkedList.add(6, 12345);
        myLinkedList.add(11, 77);
        System.out.println("\n 全部: " + myLinkedList.toString());

        myLinkedList.removeFirst();
        myLinkedList.removeFirst();
        System.out.println("\n 全部: " + myLinkedList.toString());

        System.out.println("\n size: " + myLinkedList.size());

        myLinkedList.removeLast();
        myLinkedList.removeLast();
        System.out.println("\n 全部: " + myLinkedList.toString());

        System.out.println("\n size: " + myLinkedList.size());

        System.out.println("remove :" + myLinkedList.remove(3));
        System.out.println("\n 全部: " + myLinkedList.toString());

        System.out.println("\n size: " + myLinkedList.size());
        System.out.println("\n 全部: " + myLinkedList.toString());

        System.out.println("\n contains: " + myLinkedList.contains(3));
        
        System.out.println("get "+myLinkedList.get(6));
        /*System.out.println("\n 全部: " + myLinkedList.hasNext());
        System.out.println("\n while ");
        while(myLinkedList.hasNext()){
            System.out.print(myLinkedList.next()+" \t");
        }*/
        
        
        //System.out.println("\n 全部: " + myLinkedList.hasNext());
        
        System.out.println("\n 全部: iterator================ " );
        
        MyIterator<Integer> iterator = myLinkedList.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+" \t");
        }
        
        MyIterator<Integer> iterator1 = myLinkedList.iterator();
        //System.out.println("\n hasnext:   "+iterator1.hasNext()+" size "+myLinkedList.size());
        
        System.out.println("\n next : "+iterator1.next());
        System.out.println("next : "+iterator1.next());
        System.out.println("hasPrevious : "+iterator1.hasPrevious());
        System.out.println("previous :"+iterator1.previous());
    }

}
image.png
image.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Spring Cloud為開(kāi)發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見(jiàn)模式的工具（例如配置管理，服務(wù)發(fā)現(xiàn)，斷路器，智...
    卡卡羅2017閱讀 136,632評(píng)論 19贊 139
  • 在經(jīng)過(guò)一次沒(méi)有準(zhǔn)備的面試后，發(fā)現(xiàn)自己雖然寫(xiě)了兩年的android代碼，基礎(chǔ)知識(shí)卻忘的差不多了。這是程序員的大忌，沒(méi)...
    猿來(lái)如癡閱讀 3,122評(píng)論 3贊 10
  • 一.線性表 定義:零個(gè)或者多個(gè)元素的有限序列。也就是說(shuō)它得滿足以下幾個(gè)條件:??①該序列的數(shù)據(jù)元素是有限的。??②...
    Geeks_Liu閱讀 2,768評(píng)論 1贊 12
  • 迷鹿mirror閱讀 189評(píng)論 0贊 1
  • 文 |莊姜姜 圖片來(lái)源|pinterest 當(dāng)我懷孕時(shí)，曾聽(tīng)不少過(guò)來(lái)人說(shuō)： 生完寶寶才會(huì)意識(shí)到懷孕時(shí)光太幸福，帶起...
    原子?jì)屵?/span>閱讀 363評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容