자료구조 연결 리스트(Linked List) 자바로 구현

1. 개요

연결 리스트는 데이터를 노드에 담아, 포인터로 연결해서 사용하는 자료구조다.

Ex) 첫번째 노드의 포인터로 두번째 데이터를 찾을 수 있다. 두번째 노드의 포인터로 세번째 데이터를 찾을 수 있다.

 

그리고 연결 리스트는 배열 리스트와 다른 장단점이 있다.

 

장점

• 메모리 효율성이 좋다. (배열 리스트는 배열의 크기를 선언해야 생성할 수 있다. 연결 리스트는 데이터의 숫자만큼만 메모리를 사용하면 되니, 메모리의 낭비가 적다.)
• 포인터를 통해, 노드들이 연결되어 있으니 추가, 삭제가 용이하다. (포인터로 이어져 있으니 포인터만 수정해주면 된다.)

단점

• 원하는 데이터가 들어간 노드를 찾을 때까지, 포인터로 계속 탐색해야 하니 탐색 시간이 오래 걸린다

 

 

 

 

우선 이 LinkedList는 Head 노드를 더미로 한다.

즉 값이 얼마나 들어가든 가장 앞의 노드의 값은 비어있다. 이유는 그래야 구현하기 쉽기 때문이다.

 

우선 노드 기반이라 노드부터 만들어야 한다.

 

 

2. 구현

package Structure;

public interface IList<T> {

    void add(T t);

    void insert(int index, T t);

    void clear();

    boolean delete(T t);

    boolean deleteByIndex(int index);

    T get(int index);

    int indexOf(T t);

    boolean isEmpty();

    boolean contains(T t);

    int size();
}

package Structure;

public class MyLinkedList<T> implements IList<T> {

    private int size;
    private Node head;

    public MyLinkedList() {
        this.size = 0;
        this.head = new Node(null); // dummy head node
    }

    @Override
    public void add(T t) {
        Node curr = this.head;
        while (curr.next != null){
            curr = curr.next; // curr의 next가 null이라는 건 뒤가 없다는 것
        }
        Node node = new Node(t);
        curr.next = node;
        this.size++;
    }

    @Override
    public void insert(int index, T t) {
        if (index > this.size || index < 0) { // index와 size가 같으면 add랑 같음
            throw new IndexOutOfBoundsException();
        }
        Node prev = this.head;
        Node curr = prev.next;

        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            curr = curr.next;
        }

        Node node = new Node(t, curr);
        prev.next = node;
        this.size++;
    }

    @Override
    public void clear() {
        this.size = 0;
        this.head.next = null; // next가 없으면 찾아갈 방법이 없으니 쓰레기 수집기가 수거
    }

    @Override
    public boolean delete(T t) { // 데이터가 일치하면 삭제
        Node prev = this.head;
        Node curr = prev.next;
        while (curr != null) {
            if (curr.data.equals(t)) {
                prev.next = curr.next;
                curr.next = null;
                this.size--;
                return true;
            }
            prev = prev.next;
            curr = curr.next;
        }
        return false;
    }

    @Override
    public boolean deleteByIndex(int index) {
        if (index >= this.size || index < 0) { 
            throw new IndexOutOfBoundsException();
        }
        Node prev = this.head;
        Node curr = prev.next;

        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            curr = curr.next;
        }

        prev.next = curr.next;
        curr.next = null;
        this.size--;
        return true;
    }

    @Override
    public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        Node curr = this.head.next; // 여기가 첫 데이터
        int i = 0; // 노드의 변경이 있을 때만 prev 필요
        while (i++ < index) {
            curr = curr.next;
        }
        return curr.data;
    }

    @Override
    public int indexOf(T t) {
        Node curr = this.head.next;
        int index = 0;
        while (curr != null) {
            if (t.equals(curr.data)) {
                return index;
            }
            curr = curr.next;
            index++;
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;
    }

    @Override
    public boolean contains(T t) {
        Node curr = head.next;
        while (curr != null) {
            if (t.equals(curr.data)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    @Override
    public int size() {
        return this.size; // 하나씩 뒤지면 O(N)의 시간 소요
    }

    private class Node {
        T data;
        Node next;

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

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

3. 설명

3-1. 노드

제네릭 타입의 data와 자신과 같은 객체를 받는 next를 가지고, 파라미터로 제네릭 타입, 즉 들어오는

타입에 따라 그 데이터가 data에 들어가게 된다.

 

파라미터로 next, 즉 자신과 같은 객체가 들어오면 그 객체가 next가 된다.

 

data는 내용물, next는 next pointer 가 된다.

 

 

메소드를 하나씩 살펴보면

3-2. 생성자

LinkedList의 크기를 나타내는 size, 구현을 편하게 하게 할 더미 노드, head는 null로 만든다.

 

 

3-3. add

LinkedList에서 데이터를 추가하려면 가장 끝에 있는 데이터까지 가서, 그 데이터의 넥스트 포인터를 새로운

객체로 설정해야 한다.

 

객체가 들어오면 현재 객체를 나타내는 curr 에 head를 집어넣는다.

그리고 curr의 next가 null이란 건, 뒤에 객체가 없는 tail, 마지막 객체를 뜻하는 것이고, 그 객체가 나올 때까지

curr의 넥스트 포인터로 이동한다 (O(N)의 시간복잡도)

 

tail을 찾으면 while문을 종료하고, add 메소드의 인수인 t가 담긴 노드를 생성한다.

 

그리고 tail의 넥스트 포인터에 t가 담긴 노드를 넣고, 사이즈를 하나 증가시킨다.

 

 

3-4. insert

index가 size보다 크거나, index가 음수면 에러를 일으킨다.

만약 index와 size가 같으면 add와 같은 작업을 하게 되니 에러를 발생시킬 필요는 없다.

 

 

삽입은 마지막이 아닌, 인덱스 번호까지 찾아가서 객체를 집어넣는 것이다

LinkedList 에서 객체를 삽입하는 방법은 집어넣을 노드를 a, 그 자리에 있던 노드를 b, b의 넥스트 포인터가 c

라고 할 때, b의 넥스트 포인터를 a로 바꾸고, a의 넥스트 포인터를 c로 설정하는 것이다.

 

이 작업을 하기 위해선, 노드가 3개 필요하니, 삽입 시, b가 되는 prev, c가 되는 curr을 생성한다.

 

만약 빈 LinkedList라면 while문이 돌지 않으니 head의 넥스트가 a가 되고, size가 증가하고 끝이다. O(N)

 

index가 8일 경우, prev는 8번째 노드, curr은 prev의 next가 된다.

 

그 상태에서, data가 t, next가 curr인 노드가 만들어지고, prev의 next가 t가 들어간 노드가 되고, 사이즈가

증가하면서 삽입이 끝난다.

 

 

3-5. clear

클리어는 LinkedList의 내용물을 다 지우는 것이다. 시간복잡도 O(1)

 

자바에선 어디에서도 참조되지 않는 데이터는 쓰레기 수집기에 의해 없어진다.

노드의 경우, 넥스트를 통해 참조되고 있었는데, 데이터가 비어있는 head의 넥스트가 null이 되면서

뒤에 있는 노드들은 참조되지 않게되어 없어지고, 남은 노드는 비어있으므로 LinkedList가 비게 된다.

 

 

3-6. delete

삭제의 경우, 메소드의 인수와 같은 데이터가 LinkedList 내에 있으면 삭제하는 메소드다.

curr은 next이니, null일때까지 while을 돌려라는 건, 나올때까지 뒤져란 말이다. O(N)

 

만약 curr의 데이터 부분과 인수인 t가 같으면, curr을 가르키고 있던 prev의 넥스트를 curr의 넥스트로

바꾼다. 그럼 curr은 아무에게도 참조받지 못하니 쓰레기 수집기에 의해 사라지게 된다.

 

curr뒤에 노드가 있을수도 있으니 curr의 next까지 없애서 고립시켜 준다.

 

노드가 하나 없어질 거니, 사이즈를 줄이고, 삭제에 성공했다는 true를 반환한다.

 

만약 이 과정에서 t와 같은 노드가 나오지 않는다면, 삭제에 실패했다는 false를 반환한다.

 

 

3-7. deleteByIndex

index 위치에 있는 노드를 삭제하는 메소드다.

시작부터 인덱스가 size보다 크거나, 음수일 경우 에러를 일으키게 한다.

 

인덱스 번호까지 이동하면 그 후는 delete와 같다. 시간복잡도 O(N)

prev의 next가 curr의 next가 되고, curr의 next가 null이 되니, curr은 데이터만 있고 참조받지도,

참조하지도 못하는 상태가 되어 사라진다.

 

크기 하나 줄고 성공했으니 true를 반환한다.

 

 

3-8. T get

get은 index번호에 있는 데이터 T를 반환하는 메소드다.

 

인덱스가 사이즈보다 크거나 같거나, 인덱스가 음수면 에러를 일으킨다.

 

curr은 head의 넥스트, 데이터가 들어간 노드다.

인덱스 수만큼 이동하고, 그 노드의 데이터를 반환한다. O(N)

 

3-9. indexOf

인수인 t와 같은 노드가 있는지 뒤져보고 있으면 그 인덱스를, 없으면 -1을 반환하는 메소드다.

 

curr에 데이터가 있는 노드를 집어넣고, 넥스트가 없는 데이터, 테일까지 while문을 돌리고, 노드의 데이터가

인수인 t와 같으면 그 인덱스를 반환, 결국 안나오면 -1 반환  O(N)

 

 

3-10. isEmpty

boolean이니 head의 next가 없으면 true (비었다), next가 있으면 false를 반환한다. O(1)

 

 

3-11. contains

인수인 t가 LinkedList에 포함되는지 확인한다.

 

curr은 데이터가 있는 첫번째 노드, 넥스트가 없을 때까지 같은 값이 있나 뒤져보고, 같은 값이 있으면 true,

없으면 false를 반환한다. O(N)

 

 

3-12. size

LinkedList의 크기인 size를 반환한다. O(1)

 

 

이렇게 자바로 LinkedList를 구현하고 기능을 설명해봤다.

자료구조의 기능을 이해하려면 직접 만들어 보는 게 가장 빠르다고 생각한다.