一個LinkedList的實現(xiàn)，非java util 的實現(xiàn)，沒有用java util容器，純實現(xiàn)過程，主要看算法。

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package linkedlisttest;

/**
 *
 * @author Lindily
 */
public class LinkedList<E> {

    int size = 0;
    Node<E> head = new Node(null, null, null);

    public LinkedList() {
        head.next = head.previous = head;
    }

    public void add(E node) {
        //核心 循環(huán)雙向鏈表
        Node<E> newNode = new Node(head.previous, node, head);   //新節(jié)點的prev指向頭結(jié)點的prev 新節(jié)點的next指向頭結(jié)點
        newNode.previous.next = newNode;    //調(diào)整，新節(jié)點的前一個的后一個
        newNode.next.previous = newNode;    //調(diào)整，新節(jié)點的后一個的前一個
        size++;
    }

    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ",size:" + size);
        }
        Node node = head;
        if (index < (size >> 1)) {          //index轉(zhuǎn)為二進制帶符號向右移動一個bit，相當于index/2
            for (int i = 0; i <= index; i++) {  //head是啞元，i<=index當index=0時，返回head.next
                node = node.next;           //對頭結(jié)點進行迭代
            }
        }else{
            for(int i=size;i>index;i--){
                node=node.previous;
            }
        }
        return node;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        for (int i = 0; i < list.size; i++) {
            System.out.println(list.get(i).node);
        }
    }
}

class Node<E> {

    E node;
    Node<E> next;
    Node<E> previous;

    public Node(Node<E> previous, E node, Node<E> next) {
        this.node = node;
        this.next = next;
        this.previous = previous;
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package linkedlisttest;

/**
 *
 * @author Lindily
 */
public class SingleLinkedList<T> {

    int size = 0;
    Node<T> head, tail;

    public SingleLinkedList() {
        head = tail = null;
    }

    public void add(T node) {
        if (size == 0) {
            head = tail = new Node<T>(node, null);
        } else {
            tail.next = new Node<T>(node, null);
            tail = tail.next;
        }
        size++;
    }

    public Node<T> get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ",size:" + size);
        }
        Node<T> node = head;
        for (int i = 0; i < index; i++) {  //當index=0時，i不小于index(零不小于零)，于是直接return頭結(jié)點，與linkedList不同，head不是啞元
            node = node.next;           //對頭結(jié)點進行迭代
        }
        return node;
    }

    public int size(){
        return size;
    }

    public static void main(String[] args){
        SingleLinkedList list=new SingleLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i).node);
        }
    }
}

class Node<T> {

    T node;
    Node<T> next;

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

標簽：

版權申明：本站文章部分自網(wǎng)絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。