Linked List 구현해보기

리스트에는 연속하는 메모리 공간에 저장되어 있는 ArrayList와

 

각각의 데이터안에 다음 데이터에 대한 정보를 갖고 있어 연결되는 LinkedList가 있다.

 

각 자료구조의 특징은 다음과 같다.

 

1️⃣ ArrayList

1. 데이터가 연속적으로 나열되어 있어, 특정 인덱스의 데이터에 접근하는 경우 O(1) 로 접근할 수 있다.
2. 선형 탐색의 경우 O(n), 정렬되어 있을 때 이분탐색의 경우 O(logN) 으로 접근할 수 있다.
3. 중간 위치에 데이터를 삽입 · 삭제 하는 경우, 나머지 원소들의 위치를 옮겨야 하기 때문에 O(N) 이다.

2️⃣ LinkedList

1. 특정 인덱스에 위치한 원소에 접근하는 경우에, 순회를 해서 찾아야 하므로 O(N) 이다.
2. 단일 연결 리스트의 경우, 시작 부분에 삽입 · 삭제는 O(1)에 가능하다.
3. 단일 연결 리스트의 경우, 중간 부분에 삽입 · 삭제는 해당 노드까지 이동해야하므로 O(N) 이다.
4. 데이터를 추가할 때, 노드를 연결하는 방식으로 추가하기 때문에 고정된 크기를 갖지 않아 메모리 사용이 효율적이다.

 

 

 

단일 연결 리스트(Singly Linked List) 구현

단일 연결 리스트는 일반적으로, 첫 데이터를 참조하는 head 와 마지막 데이터를 참조하는 tail를 갖도록 구현한다.

 

이로써, 리스트의 첫번째나 마지막 데이터에 변화를 줄 때, O(1) 로 수행할 수 있게 된다.

 

Node 클래스 정의

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

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

    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }
}

연결 리스트는 Node안에 데이터를 담고

 

Node와 Node를 연결하는 방식으로 구현한다.

 

 SinglyLinkedList 클래스 정의

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

    public SinglyLinkedList() {
        this.head = this.tail = null;
    }
}

SinglyLinkedList 는 head 노드와 tail 노드를 참조를 위한 변수와 리스트 내의 원소 개수를 체크하기 위한 size 변수를 갖는다.

 

 

addFirst(E e) 메서드

먼저, 리스트의 제일 앞에 노드를 추가하기 위한 메서드를 구현할 것이다.

 

1. head 노드가 이미 존재하는 경우
   1. 추가하려는 데이터를 갖는 Node 를 정의하고, 그 Node의 next 변수에 head를 참조하도록 한다.
   2. 그리고 리스트의 head에 새롭게 추가한 Node를 참조하도록 변경한다. 
2. head 노드가 없는 경우
   1. 새롭게 추가하려는 노드를 head에 바로 참조하도록 한다.
   2. head 노드가 아직 없는 경우는, 리스트가 비어있다는 의미이므로 새롭게 추가하는 노드를 tail 변수도 참조하도록 만든다.
3. 추가 후, size 변수를 1 증가한다.

 

    public void addFirst(E e) {
        final Node node = new Node(e);
        if (head == null) {
            this.head = node;
            this.tail = node
        } else {
            node.next = this.head;
            this.head = node;
        }
        this.size++;
    }

 

addLast(E e) 메서드

리스트의 마지막에 노드를 추가하는 메서드를 구현할 것이다.

 

1. tail 노드가 이미 존재하는 경우
   1. tail 에 위치한 노드의 next 변수에 새롭게 추가하는 노드를 참조하도록 만든다.
   2. 리스트의 tail 변수에 새롭게 추가하는 노드를 참조하도록 만든다.
2. tail 노드가 없는 경우
   1. 새롭게 추가하는 노드를 tail 변수가 참조하도록 만든다.
   2. tail 노드가 null 이라는 의미는, 리스트가 비어있다는 뜻이므로 head 변수도 참조하도록 만든다.
3. 추가 후, size 변수를 1 증가한다.

    public void addLast(E e) {
        final Node node = new Node(e);
        if (this.tail == null) {
            this.tail = node;
            this.head = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    }

 

get(int idx) 메서드

특정 인덱스의 Node를 가져오는 메서드를 구현할 것이다.

 

1. idx 가 리스트 size 보다 크거나 같은 경우
   1. 해당 인덱스에 노드가 존재하지 않으므로 예외처리 해준다.
2. idx 가 0보다 작은 경우
   1. 0보다 작은 인덱스는 존재하지 않으므로 예외처리 해준다.
3. idx 가 size-1과 동일한 경우
   1. 마지막 Node이므로 tail 변수가 참조하는 Node를 반환한다.
4. idx 가 0인 경우
   1. 첫번째 Node이므로 head 변수가 참조하는 Node를 반환한다.

    public Node get(int idx) {
        if (idx < 0 || idx >= size) {
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size: " + size);
        }

        if (idx == 0) {
            return this.head;
        } else if (idx == size - 1) {
            return this.tail;
        } else {
            Node node = this.head;
            for (int i = 0; i < idx; i++) {
                node = node.next;
            }
            return node;
        }
    }

 

add(int idx, E e) 메서드

특정 인덱스에 노드를 추가하는 메서드를 구현할 것이다.

 

1. idx가 0인 경우
   1. addFirst 메서드 호출
2. idx가 리스트 size 와 동일한 경우
   1. addLast 메서드 호출
3. idx 가 0보다 작거나 size 보다 큰 경우
   1. 예를 들어, 리스트의 전체 노드 수가 2개 인데, 삽입하려는 위치가 3인 경우 불가하다. 따라서 예외처리한다.
4. 그 외
   1. 추가하려는 Node의 next 변수에 idx 위치의 Node를 참조하도록 만든다.
   2. idx-1 위치의 Node의 next 변수에 추가하려는 Node를 참조하도록 만든다.
   3. 결과적으로 idx 위치에 존재하는 Node는 새롭게 추가한 Node가 된다.
5. 추가 후 size 를 1 증가한다.

    public void add(int idx, E e) {
        if (idx < 0 || idx > size) {
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size: " + size);
        }

        if (idx == 0) {
            addFirst(e);
        } else if (idx == size) {
            addLast(e);
        } else {
            final Node node = new Node(e);
            Node previous = get(idx - 1);
            node.next = previous.next;
            previous.next = node;
            this.size++;
        }
    }

 

remove(int idx) 메서드

특정 인덱스의 노드를 삭제하는 메서드를 구현할 것이다.

 

1. idx 가 0보다 작거나 size보다 크거나 같은 경우
   1. Node가 존재하지 않으므로 예외 처리한다.
2. idx가 0인 경우
   
   1. head 변수에 head.next 변수를 할당한다.
3. idx가 size-1인 경우
   1. idx-1에 해당하는 Node에 접근해서, Node.next 를 null로 할당한다.
   2. tail 변수를 idx-1에 있던 Node 로 할당한다.
4. 그 외
   1. idx-1에 해당하는 Node에 접근해서 Node.next를 Node.next.next로 할당한다. 
5. size 를 1 감소시킨다.

    public void remove(int idx) {
        if (idx < 0 || idx >= size) {
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size: " + size);
        }

        if (idx == 0) {
            this.head = this.head.next;
        } else {
            Node node = get(idx - 1);
            if (idx == size - 1) {
                node.next = null;
                this.tail = node;
            } else {
                node.next = node.next.next;
            }
        }

        this.size--;
    }