Linked List (+ Node, Iterator ) [Java Collection 구현하기]

 

Node 클래스

public class Node<E> {
    private Node<E> next;   // 다음 노드 (null 가능)
    private E data;         // element값 == data (제네릭 타입)

    // 생성자
    public Node(E data) {
        super();
        this.data = data;
    }

    // getter: next(다음 노드) 반환
    public Node<E> next() {
        return next;
    }

    // setter: next(다음 노드) 지정
    public void next(Node<E> next) {
        this.next = next;
    }

    // setter: data(element) 지정
    public void data(E data) {
        this.data = data;
    }

    // getter: data(element) 반환
    public E data() {
        return data;
    }

    // toString
    @Override
    public String toString() {
        return data.toString();
    }
}

 

LinkedList 클래스

import c_datastructure.Node;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class _LinkedList<E> implements Iterable<E> {
    private Node<E> head;
    private int size;

    // size()
    public int size() {
        return size;
    }

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

    // CRUD
    // C: add()
    public boolean add(E e) {
        Node<E> node = new Node<>(e);
        // head가 null이면 첫번째 요소를 삽입.
        if (head == null) {
            head = node;
            size++;
            return true;
        }
        // head가 null이 아님
        // 마지막 노드(rear)는 next가 없음
        Node<E> link = head;
        while (link.next() != null) {
            link = link.next();
        }
        // 찾은 마지막 노드(link)의 옆에 넣을 노드를 추가
        link.next(node);
        size++;
        return true;
    }

    // R: get()
    public E get(int index) {
        // 잘못된 인덱스를 참조하려고 할 때
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        // 정상 인덱스라면
        Node<E> link = head;    // 노드 이동용 참조 변수
        for (int i=0; i<index; i++) {
            link = link.next();
        }

        return link.data(); // 담겨있는 데이터 반환
    }

    // Update: set()
    public E set(int index, E e) {
        // 인덱스 검사
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> link = head;
        for (int i=0; i<index; i++) {
            link = link.next();
        }
        E prev = link.data(); // 이전 데이터
        link.data(e);
        return null;
    }

    // Delete: remove()
    public E remove(int index) {
        // 인덱스 검사
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> link = head;    // 이동 추적용 변수
        Node<E> prevNode = head;    // 이전 데이터
        for (int i=0; i<index; i++) {
            prevNode = link;
            link = link.next();
        }

        prevNode.next(link.next());
        E prev = link.data();
        size--;
        return null;
    }

    // toString
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        for (int i=0; i<size; i++) {
            sb.append(get(i));
            if (i == size-1) break;
            sb.append(", ");;
        }
        sb.append(" ]");
        return sb.toString();
    }

    // Iterator
    @Override
    public Iterator<E> iterator() {
        //익명클래스 방식
        return new Iterator<E>() {
            // 현재 노드는 head부터 시작(초기화)
            private Node<E> current = head;

            @Override
            public boolean hasNext() {
                // 현재 노드가 null 이면 false 반환, null이 아니면 true 반환
                return current != null ? true: false;
            }

            @Override
            public E next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                E data = current.data();  // 현재 노드의 데이터 반환
                current = current.next(); // 현재 노드를 다음 노드로 초기화
                return data;
            }
        };
    }
}

 

 

테스트 실행용 클래스

public class Run {

    public static void main(String[] args) {
       testAdd();
       testGet();
       testSet();
       testRemove();
        testIterable();
    }

    static void testAdd() {

        _LinkedList<Integer> list = new _LinkedList<Integer>();

        for (int i = 0; i < 30; i++) {
            list.add(i);
        }

        System.out.println(list);
    }

    static void testGet() {

        _LinkedList<Integer> list = new _LinkedList<Integer>();

        for (int i = 0; i < 30; i++) {
            list.add(i);
        }

        for (int i = 5; i < 8; i++) {
            System.out.println(list.get(i));
        }
    }

    static void testSet() {
        _LinkedList<Integer> list = new _LinkedList<Integer>();

        for (int i = 0; i < 30; i++) {
            list.add(i);
        }

        for (int i = 5; i < 8; i++) {
            list.set(i, 9999);
        }

        System.out.println(list);
    }

    static void testRemove() {
        _LinkedList<Integer> list = new _LinkedList<Integer>();

        for (int i = 0; i < 30; i++) {
            list.add(i);
        }

        for (int i = 5; i < 8; i++) {
            list.remove(i);
        }

        System.out.println(list);
    }

    static void testIterable() {
        _LinkedList<Integer> list = new _LinkedList<Integer>();

        for (int i = 0; i < 10; i++) {
            list.add(i);
        }

        // 1. Iterable 인스턴스의 iterator 메서드를 호출해서 Iterator 객체를 반환 받음
        Iterator<Integer> it = list.iterator();

        // 2. hasNext를 호출해서 다음 요소가 존재하는지 확인
        while (it.hasNext()) {
            // 3. 존재하면 next()를 통해 반환받음
            Integer e = it.next();
            System.out.println(e);
        }

/*      for-each문으로 다시 테스트
        for (Integer i : list) {
            System.out.println(i);
        }*/
    }
}