[자료구조] 자바로 LinkedList 직접 구현해보기

오랜만에 손코딩 연습도 해볼겸 개념정리도 한번 할겸 자바로 링크드리스트를 구현해보았다.

링크드리스트는 노드가 연속적으로 다음 포인터를 가지고 있는 자료구조이다.

링크드 리스트의 개념이나 특징을 공부한 후에 구현해보는 것을 추천한다!

 

처음에는 데이터 타입을 그냥 가장 상위 클래스인 Object 클래스로 구현해보았다.

그렇게 하면 여러개의 다른 데이터 타입을 넣을 수는 있겠지만,

하나의 데이터 타입으로 고정할 수가 없었다. (예를 들면 자바 라이브러리 util에 있는 자료구조들처럼..)

 

그래서 제네릭 타입으로 구현하여 호출하는 쪽에서 타입을 지정하고,

다른 타입을 파라미터로 넣으면, 컴파일 오류가 나게하여 더 좋은 코드를 작성해보았다.

일반적으로, 컴파일 오류가 나게끔 하는 게 더 좋은 코드이다.
런타임 오류는 프로그램 실행 도중에 나는 오류라 위험하다.
미리 컴파일 전에 오류를 발견하여 수정할 수 있는 것이 좋다.

 

 

public class LinkedList<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size = 0;

    private class Node<E> {
        private Node<E> next;
        private E data;

        public Node(E data) {
            this.data = data;
        }
    }

    public Node<E> search(int idx) {  //idx번째 있는 노드 반환
        if(idx >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> node = head;
        for (int i = 0; i < idx; i++) {
            node = node.next;
        }
        return node;
    }

    public void addFirst(E data) {  //맨 앞에 노드 추가
        Node<E> newNode = new Node(data);

        newNode.next = head;
        head = newNode;
        size++;

        if(newNode.next == null) {
            tail = head;
        }
    }

    public void add(int idx, E data) {  //idx번째에 노드 추가
        if(idx == 0) {
            addFirst(data);
            return;
        }

        Node<E> newNode = new Node<>(data);
        Node<E> tmp = search(idx-1);
        newNode.next = tmp.next;
        tmp.next = newNode;
        size++;

        if(newNode.next == null) {
            tail = newNode;
        }
    }

    public E removeFirst() {  //맨 앞 노드 삭제
        if(head == null) {
            throw new IndexOutOfBoundsException();
        }
        E data = head.data;
        Node<E> tmp = head;
        head = tmp.next;

        tmp = null;
        size--;
        return data;
    }

    public E remove(int idx) {  //idx번째에 있는 노드 삭제
        if(idx >= size) {
            throw new IndexOutOfBoundsException();
        }
        if(idx == 0) {
            return removeFirst();
        }

        Node<E> node = search(idx-1);
        Node<E> deleted = node.next;

        node.next = deleted.next;
        E data = deleted.data;
        deleted = null;
        size--;

        if(node.next == null) {
            tail = node;
        }
        return data;
    }

    public void print() {  //모든 노드의 데이터 순서대로 출력
        if(head == null) {
            System.out.println("x");
            return;
        }

        Node<E> node = head;
        while(node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    public void printInfo() {  //현재 head, tail의 데이터와 size 출력
        if(size == 0) return;
        System.out.println("head : " + head.data + ",tail : " + tail.data + ",size : " + size);
    }
}

링크드리스트는 head와 tail, size를 가지고 있으며, 각 노드는 다음 노드 정보와 데이터를 가지고 있다.

여러가지 예외 처리는 적당히만 구현했다.

 

혹시 잘못된 부분 있으면 피드백 부탁드립니다!