Java 中的基本 SinglyLinkedList 示例

java 中單連結列表的基本實現 - 可以將整數值新增到列表末尾，從列表中刪除遇到的第一個值，在給定時刻返回值陣列並確定給定值是否存在在列表中。

Node.java

package com.example.so.ds;

/**
 * <p> Basic node implementation </p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.1
 */
public class Node {
    
    private Node next;
    private int value;
    
    public Node(int value) {
        this.value=value;
    }

    public Node getNext() {
        return next;
    }

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

    public int getValue() {
        return value;
    }
    
    
}

SinglyLinkedList.java

package com.example.so.ds;

/**
 * <p> Basic single-linked-list implementation </p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.2
 */
public class SinglyLinkedList {
    
    private Node head;
    private volatile int size;
    
    public int getSize() {
        return size;
    }
    
    public synchronized void append(int value) {
        
        Node entry = new Node(value);
        if(head == null) {
            head=entry;
        }
        else {
            Node temp=head;
            while( temp.getNext() != null) {
                temp=temp.getNext();
            }
            temp.setNext(entry);
        }
        
        size++;
    }
    
    
    public synchronized boolean removeFirst(int value) {
        boolean result = false;
        
        if( head == null ) { // or size is zero..
            // no action
        }
        else if( head.getValue() == value ) {
            head = head.getNext();
            result = true;
        }
        else {

            Node previous = head;
            Node temp = head.getNext();
            while( (temp != null) && (temp.getValue() != value) ) {
                previous = temp;
                temp = temp.getNext();
            }
            
            if((temp != null) && (temp.getValue() == value)) { // if temp is null then not found..
                previous.setNext( temp.getNext() );
                result = true;
            }

        }
        
        if(result) {
            size--;
        }
        
        return result;
        
    }
    
    public synchronized int[] snapshot() {
        Node temp=head;
        int[] result = new int[size];
        for(int i=0;i<size;i++) {
            result[i]=temp.getValue();
            temp = temp.getNext();
        }
        return result;
    }
    
    public synchronized boolean contains(int value) {
        boolean result = false;
        Node temp = head;
        
        while(temp!=null) {
            if(temp.getValue() == value) {
                result=true;
                break;
            }
            temp=temp.getNext();
        }
        return result;
    }
    
}

TestSinglyLinkedList.java

package com.example.so.ds;

import java.util.Arrays;
import java.util.Random;

/**
 * 
 * <p> Test-case for single-linked list</p>
 * @since 20161008
 * @author Ravindra HV
 * @version 0.2
 *
 */
public class TestSinglyLinkedList {

    /**
     * @param args
     */
    public static void main(String[] args) {
        
        SinglyLinkedList singleLinkedList = new SinglyLinkedList();
        
        int loop = 11;
        Random random = new Random();
        
        for(int i=0;i<loop;i++) {
            
            int value = random.nextInt(loop);
            singleLinkedList.append(value);

            System.out.println();
            System.out.println("Append :"+value);
            System.out.println(Arrays.toString(singleLinkedList.snapshot()));
            System.out.println(singleLinkedList.getSize());
            System.out.println();
        }
        
        for(int i=0;i<loop;i++) {
            int value = random.nextInt(loop);
            boolean contains = singleLinkedList.contains(value);
            singleLinkedList.removeFirst(value);
            
            System.out.println();
            System.out.println("Contains :"+contains);
            System.out.println("RemoveFirst :"+value);
            System.out.println(Arrays.toString(singleLinkedList.snapshot()));
            System.out.println(singleLinkedList.getSize());
            System.out.println();
        }
        

    }

}