Linked List (단순 연결 리스트) 소스

 
public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
 
    private class Node {
 
        private Object data;
        private Node next;
 
        // 변수타입을 가지고 있어야함
        public Node(Object input) {
            this.data = input;
            this.next = null;
 
        }
 
        public String toString() {
 
            return String.valueOf(this.data);
        }
    }
 
    // 머리에다가 추
    public void addFirst(Object input) {
        Node newNode = new Node(input);
        newNode.next = head;
        head = newNode;// 방금 생성한 노드를 head로
        size++;
 
        // 다음노드가 존재하지 않는다는
        if (head.next == null) {
            tail = head;
        }
 
    }
 
    public void addLast(Object input) {
        Node newNode = new Node(input);
        if (size == 0) {
            addFirst(input);
        } else {
            tail.next = newNode;
            tail = newNode;
            size++;
        }
 
    }
 
    // 내부적으로 사용할것 (test를 위해 public)
    Node node(int index) {
        // 첫번째 노드를 찾아오는 것이고 그게 헤드이다.
        Node x = head;
 
        // 다음 노드들을 가지고 오기 위해서 next를 인덱스만큼 반복
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }
 
    public void add(int k, Object input) {
        if (k == 0) {
            addFirst(input);
        } else {
            // 추가시키지 이전 노드를 알고있어야함
            Node temp1 = node(k - 1);
            // 밀어질 노드에 대한 정보
            Node temp2 = temp1.next;
            Node newNode = new Node(input);
            temp1.next = newNode;
            newNode.next = temp2;
            size++;
            // 뒤에 널이면 테일로 바준닷.
            if (newNode.next == null) {
                tail = newNode;
            }
        }
    }
 
    public String toString() {
        if (head == null) {
            return "[]";
        }
        Node temp = head;
        String str = "[";
 
        while (temp.next != null) {
            str += temp.data + ",";
            temp = temp.next;
        }
        str += temp.data;
 
        return str + "]";
 
    }
 
    // 자바에서는 컬렉션 프레임웍은 삭제된 노드의 값을 리턴해주게된다.
    public Object removeFirst() {
        Node temp = head;
        head = head.next;
        Object returnData = temp.data;
        temp = null;
        size--;
        return returnData;
    }
 
    // 노드 삭제하기
    public Object remove(int k) {
        if (k == 0) {
            return removeFirst();
        }
        Node temp = node(k - 1);
        Node todoDeleted = temp.next;
        temp.next = temp.next.next;
        Object returnData = todoDeleted.data;
        if (todoDeleted == tail) {
            tail = temp;
        }
        todoDeleted = null;
        size--;
        return returnData;
    }
 
    // 마지막 노드 삭제 테일만 지우면 이것저것 효과가 없어진닷;
    public Object removeLast() {
        return remove(size - 1);
    }
 
    // 사이즈 호출하기
    public int size() {
        return size;
    }
 
    // 특정한 위치의 데이터 가져오기
    public Object get(int k) {
        Node temp = node(k);
        return temp.data;
    }
 
    public int indexOf(Object data) {
        Node temp = head;
        int index = 0;
        while (temp.data != data) {
            temp = temp.next;
            index++;
            if (temp == null) {
                return -1;
            }
 
        }
        return index;
    }
 
    public ListIterator listIterator() {
        return new ListIterator();
    }
 
    public class ListIterator {
        private Node next;
        private Node lastReturned;
        // 몇번째 있는가 알필요가 있고, hasNext할때 필
        private int nextIndex;
 
        ListIterator() {
            next = head;
        }
 
        public Object next() {
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.data;
 
        }
 
        public boolean hasNext() {
            return nextIndex < size();
        }
 
        public void add(Object input) {
            Node newNode = new Node(input);
 
            if (lastReturned == null) {
                head = newNode;
                newNode.next = next;
            } else {
 
                lastReturned.next = newNode;
                newNode.next = next;
            }
            
            lastReturned = newNode;
            nextIndex++;
            size++;
 
        }
        
        public void remove() {
            if(nextIndex == 0) {
                throw new IllegalStateException();
            }
            //비효율적이다. 노드를 찾았는데또 찾음!;
            LinkedList.this.remove(nextIndex-1);
            nextIndex--;
        }
    }
 
}
 

Main.java

 
public class Main {
 
    public static void main(String[] args) {
        LinkedList numbers = new LinkedList();
//        numbers.addFirst(30);
//        numbers.addFirst(20);
//        numbers.addFirst(10);
//        
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
//        numbers.add(1, 15);
//        numbers.removeFirst();
        //특정한위치에
//        numbers.add(2,25);// 20은 뒤로밀린다.
//        System.out.println(numbers);
        
        //head삭
//        System.out.println(numbers.removeFirst());
//        System.out.println(numbers);
//        System.out.println(numbers.remove(0));
//        System.out.println(numbers.size());
//        System.out.println(numbers.get(2));
//        System.out.println(numbers.indexOf(30));
        LinkedList.ListIterator i = numbers.listIterator();
//        System.out.println(i.next());
//        System.out.println(i.hasNext());
        //        System.out.println(numbers.node(2));
 
        //hasNext호출을 위한 메소드 
//        while(i.hasNext()) {
//            System.out.println(i.next());
//    }
        
        //head에 노드 추가하
//        i.add(5);
//        i.next();
//        중간에 노드 추가하기 
//        i.add(15);
//        System.out.print(numbers);
    
        i.next();
        i.remove();
    
    }
        
 
}
 

출처 : 생활코딩