LinkedList 직접 구현해 보기

요약 정리

LinkedList(연결 리스트)를 구현하기 앞서 해당 자료 구조에 대해 알아보자.

우선 List라고 하면 인덱스 구조로 위치를 갖고, 순서를 보장하는 자료구조라고 설명할 수 있겠다.

더 나아가 LinkedList는 삽입 / 삭제의 장점을 갖지만, 특정 노드 탐색시 다른 List에 비해 오래 걸린다는 단점이 있다.

 

삽입 / 삭제의 장점을 갖을 수 있는 이유는 LinkedList의 종류에 따라 다르지만, 모두 노드의 연결로 이루어져 있으며 인접 노드의 주소를 포인터로 가르키고 있어 중간에 삽입 / 삭제가 이루어 져도 해당 노드를 끊고 인접 노드의 주소를 연결해 주면 될뿐 대표적인 ArrayList처럼 데이터를 미루거나 당기는 작업이 필요 없다.

 

LinkedList에는 Singly, Doubly, Circular 세가지 종류가 있다.

Singly LinkedList : 단방향 연결 리스트로 다음 노드의 주소를 가르키는 구조이다.

Doubly LinkedList : 양방향 연결 리스트로 이전/다음 노드의 주소를 가르키는 구조이다.

Circular LinkedList : 원형 연결 리스트로 추가적으로 처음, 마지막 노드가 주소를 가르키고 있는 구조이다.

 

구현

가장 기본형인 Singly LinkedList 의 메서드를 구현했다. 
위에서 언급하였듯 다음 노드의 주소를 포인터로 가르키는 구조이기 때문에 next라는 필드로 다음 노드를 참조하도록 구성했다.

 

노드의 구성

- 현재 노드의 data를 저장할 data필드, 다음 노드를 참조할 next 필드를 정의하였다.

- 클래스 내부에서 사용할 데이터 타입을 외부에서 지정하기 위해 Generic을 사용하였다.

- Node 객체 비교가 필요할 경우를 대비하여 equals와 hashCode를 재정의하였다.

- 추후 LinkedList에서 StringBuilder를 통해 객체의 모든 요소를 출력하기 위해 toString을 재정의하였다.

   public class Node<T> {
        private T data;
        private Node<T> next = null;

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

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?> node = (Node<?>) o;
            return Objects.equals(data, node.data) && Objects.equals(next, node.next);
        }

        @Override
        public int hashCode() {
            return Objects.hash(data, next);
        }

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

 

가장 첫번째 노드를 저장할 Head 필드 구성

- static inner class로 노드를 사용 (Effective Java 3판 item24 참조)

• • static을 생략하면 바깥 인스턴스로의 숨은 외부 참조를 갖게 된다.
  • static을 생략하면 GC가 바깥 클래스의 인스턴스를 수거하지 못하는 메모리 누수가 생길 수 있다.

public class SimpleLinkedList<T> {
    private Node<T> head = null;
    private static class Node<T> {
        ...
    }
}

 

SimpleLinkedList 구성

package Algorithms.자료구조.LinkedList;

import java.util.NoSuchElementException;
import java.util.Objects;

public class SimpleLinkedList<T> {

    private Node<T> head = null;
    
    private static class Node<T> {
    
        private T data;
        private Node<T> next = null;

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

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?> node = (Node<?>) o;
            return Objects.equals(data, node.data) && Objects.equals(next, node.next);
        }

        @Override
        public int hashCode() {
            return Objects.hash(data, next);
        }

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

    // Node 추가 메서드
    public void add(T data) {
        // 첫번째 일 경우
        if(head == null) head = new Node<>(data);
        else {
            Node<T> node = this.head;
            while (node.next != null) node = node.next;
            // 마지막 노드를 탐색하여 인스턴스 생성
            node.next = new Node<>(data);
        }
    }

    // 노드 중간 삽입 메서드
    public void add(int index, T data) {
        if(index < 0) throw new IndexOutOfBoundsException("index can't smaller then 0");
        // 0번쨰 index라면 head 변경과 동일
        if(index == 0) {
            addFirst(data);
            return;
        }
        Node<T> temp = search(index);
        Node<T> node = new Node<>(data);
        node.next = temp.next;
        temp.next = node;
    }
	
    // 노드삭제
    public void remove(int index) {
        if(this.head == null) {
            if(0 < index) throw new IndexOutOfBoundsException("Index bigger then size");
            throw new NoSuchElementException("First Node is Empty");
        }
        // 첫번째 요소라면 헤드를 변경
        if(index == 0) {
            head = head.next;
            return;
        }
        int n = 1;
        Node<T> node = this.head;
        while (n < index) {
            if(node == null) {
                throw new IndexOutOfBoundsException("index bigger then size");
            }
            node = node.next;
            n++;
        }
        node.next = node.next == null ? null : node.next.next;
    }

    public void addFirst(T data) {
        if(this.head == null) throw new IndexOutOfBoundsException("index bigger then size");
        Node<T> node = new Node<>(data);
        node.next = this.head;
        this.head = node;
    }

    public void addLast(T data) {
        add(data);
    }

    public Integer indexOf(T data) {
        if(this.head == null) return null;
        int n = 0;
        Node<T> node = this.head;
        while (node != null) {
        	// 노드의 요소와 찾는 요소가 같다면 return
            if (node.data == data) return n;
            node = node.next;
            n++;
        }
        return null;
    }

    // 노드 순회
    private Node<T> search(int index) {
        if(this.head == null) throw new IndexOutOfBoundsException("index bigger then size");
        int n = 1;
        Node<T> node = this.head;
        while (n < index) {
            node = node.next;
            if (node == null) throw new IndexOutOfBoundsException("index bigger then size");
            n++;
        }
        return node;

    }

    @Override
    public String toString() {
        /*
        배열의 형식 구성
        ex) [1, 2, 3, ... , n]
        */
        StringBuilder stringBuilder = new StringBuilder("[");
        Node<T> node = this.head;
        stringBuilder.append(node);
        while (node.next != null) {
            //모든 노드 탐색
            node = node.next;
            stringBuilder.append(", ").append(node);
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}

 

Main 메서드를 이용한 메서드 테스트

package Algorithms.자료구조.LinkedList;

public class Main {
    public static void main(String[] args) {

        SimpleLinkedList<Integer> simpleLinkedList = new SimpleLinkedList<>();
        simpleLinkedList.add(4);
        simpleLinkedList.add(0,2);
        simpleLinkedList.add(1,3);
        simpleLinkedList.add(0,3);
        System.out.println(simpleLinkedList);
        simpleLinkedList.addFirst(1);
        simpleLinkedList.addLast(5);
        System.out.println(simpleLinkedList);

        simpleLinkedList.remove(simpleLinkedList.indexOf(3));
        System.out.println(simpleLinkedList);
    }
}

 

 

간단한 동작 구현이라 예외 처리가 부족한 부분이 있을 수 있습니다. 긴 글 읽어 주셔서 감사합니다 :)