[면접을 위한 CS 전공지식 노트][자료구조] 연결리스트 LinkedList

0. 개요

 이전 글에서는 선형 자료구조인 배열의 구조와 Java에서의 ArrayList를 살펴보았다. 이번에는 연결리스트에 대해서 공부한 내용을 글로 정리하여 남기고자 한다.

 일단 연결리스트에는 단방향 연결리스트와 양방향 연결리스트가 있다. 이번 글에서는 두 가지 모두에 대해서 구현해보고, 특징들에 대해서 알아볼 예정이다.

 

1. 단방향 연결리스트

 단방향 연결리스트는 말 그대로 한 방향으로만 링크된 리스트들을 의미한다. 즉, 앞에서 뒤로는 탐색이 가능하지만, 역방향으로는 탐색이 불가능하다. 그림으로 살펴보자.

 아래 그림과 같이 Head는 다음 노드를 가리키고 있고, 0번 노드는 1번 Tail을 가리키고 있다. 그러나 Tail에서 0번 노드의 주소는 알지 못하기 때문에 역방향의 탐색이 불가능하다.

 

2. 양방향 연결리스트

 반면 양방향 연결리스트는 tail로 부터 역방향의 탐색이 가능하다.

Head 부터 Tail 까지 각각 다음 노드를 가리키고 있고, Tail에서 Head까지도 각각 이전 노드를 가리키고 있기 때문에, 양방향으로 탐색이 가능하다.

3.  코드 구현

LinkedList에서 구현할 메서드 명세 선언.

public interface IList<T> {
    /**
     * 엘리먼트 추가
     * @param t
     */
    void add(T t);

    /**
     * 엘리먼트 삽입
     * @param index
     * @param t
     */
    void insert(int index, T t);

    /**
     * 엘리먼트 전부 삭제
     */
    void clear();

    /**
     * 해당 엘리먼트 삭제
     * @param t
     * @return
     */
    boolean delete(T t);

    /**
     * 인덱스를 이용한 엘리먼트 삭제
     * @param index
     * @return
     */
    boolean deleteByIndex(int index);

    /**
     * 인덱스에 해당하는 엘리먼트 가져오기
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 해당 엘리먼트의 인덱스 가져오기
     * @param t
     * @return
     */
    int indexOf(T t);

    /**
     * 비어있는지 확인
     * @return
     */
    boolean isEmpty();

    /**
     * 해당 엘리먼트가 포함되어 있는지 확인
     * @param t
     * @return
     */
    boolean contains(T t);

    /**
     * 현재 사이즈 가져오기
     * @return
     */
    int size();
}

 

단방향 연결리스트 구현.

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

    private int size;

    private Node head;

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

    // 노드가 null을 가리키고 있을 때까지 순회 후 null일 경우, 현재 값을 add해주고 종료
    @Override
    public void add(T t) {
        Node current = this.head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(t);
        this.size++;
    }

    // 해당 인덱스 까지 투포인터로 prev, curr를 가지고 가다가 인덱스에 도착하면 prev와 curr사이에 넣고 종료
    @Override
    public void insert(int index, T t) {
        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;
        }
        Node node = new Node(t, curr);
        prev.next = node;
        this.size++;
    }

    // head에 연결된 link를 끊고 사이즈를 0으로 만든다.
    @Override
    public void clear() {
        this.size = 0;
        this.head.next = null;
    }

    // prev, curr로 투포인터로 탐색해가면서 같은 값을 찾으면, prev와 curr.next를 연결해주고, curr이 가리키는 포인터를 null로 변경 후 사이즈 --
    @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;
    }

    // prev와 curr 투포인터로 계속 탐색 진행하다가 해당 인덱스 도착하면 prev와 curr.next를 연결해주고, curr은 null을 가리키게 변경후 사이즈 --
    @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;
    }

    // 순회하면서 index에 해당하는 노드에 도착할 경우 data를 리턴
    @Override
    public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        Node curr = this.head.next;

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

    // node의 data가 t와 같은지 확인하면서 처음 부터 순회 후 같은 것을 찾으면 현재 인덱스를 리턴, 없을 경우 -1
    @Override
    public int indexOf(T t) {
        Node curr = this.head.next;

        int i = 0;
        while (curr != null){
            if(curr.data.equals(t)){
                return i;
            }
            curr= curr.next;
            i++;
        }

        return -1;
    }

    // 더미헤드가 가리키고 있는 다음 엘리먼트가 null인지 확인
    @Override
    public boolean isEmpty() {
        return this.head.next == null;
    }

    // 순회하면서 t가 존재하는지 확인 후 있으면 true 없으면 false
    @Override
    public boolean contains(T t) {
        Node curr = this.head.next;
        while (curr != null){
            if(curr.data.equals(t)){
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    // this.size를 리턴
    @Override
    public int size() {
        return this.size;
    }

    private class Node {
        T data;
        Node next;

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

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

 

양방향 연결리스트 구현.

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


    private Node head;
    private Node tail;
    private int size;

    public MyDoubleLinkedList() {
        this.size = 0;
        this.head = new Node(null);
        this.tail = new Node(null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size++;
    }

    @Override
    public void add(T t) {
        Node last = this.tail.prev;
        Node node = new Node(t, last, this.tail);
        last.next = node;
        this.tail.prev = node;
        this.size++;
    }

    @Override
    public void insert(int index, T t) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        Node prev = null;
        Node curr = null;

        if (index < this.size / 2) {
            prev = this.head;
            curr = prev.next;

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

            int i = 0;
            while (i++ < (this.size - index)) {
                curr = curr.prev;
                prev = prev.prev;
            }
        }
        Node node = new Node(t, prev, curr);
        prev.next = node;
        curr.prev = node;
        size++;

    }

    @Override
    public void clear() {
        this.size = 0;
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    @Override
    public boolean delete(T t) {

        return false;
    }

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


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

            prev.next = curr.next;
            curr.next.prev = prev;
            curr.next = null;
            curr.prev = null;
        } else {
            next = this.tail;
            curr = next.prev;

            while (i++ < (this.size - index) - 1) {
                next = next.prev;
                curr = curr.prev;
            }
            next.prev = curr.prev;
            curr.prev.next = next;
            curr.next = null;
            curr.prev = null;
        }
        this.size--;
        return false;
    }

    @Override
    public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        int i = 0;
        Node curr = null;
        if (index < this.size / 2) { // 인덱스가 head에서 더 가까울때
            curr = this.head.next;

            while (i++ < index) {
                curr = curr.next;

            }
        } else { // 인덱스가 tail에서 더 가까울 때
            curr = this.tail.prev;
            i = 0;
            while (i++ < (this.size - index) - 1) {
                curr = curr.prev;
            }
        }

        return curr.data;
    }

    @Override
    public int indexOf(T t) {
        Node head = this.head.next;
        Node tail = this.tail.prev;

        int i = 0;

        int count = this.size % 2 == 0 ? this.size / 2 : this.size / 2 + 1;

        while (i++ <= count) {
            if (head.data.equals(t)){
                return i-1;
            }
            if(tail.data.equals(t)){
                return this.size-i;
            }
            head = head.next;
            tail = tail.prev;
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {
        return this.size==0;
    }

    @Override
    public boolean contains(T t) {

        Node head = this.head.next;
        Node tail = this.tail.prev;

        int i = 0;

        int count = this.size % 2 == 0 ? this.size / 2 : this.size / 2 + 1;

        while (i++ <= count) {
            if (head.data.equals(t) || tail.data.equals(t)){
                return true;
            }
            head = head.next;
            tail = tail.prev;
        }
        return false;
    }

    @Override
    public int size() {
        return this.size;
    }

    private class Node {
        T data;
        Node prev;
        Node next;

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

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

 

4. 시간복잡도

자료구조	접근	탐색	삽입	삭제	비고
이중연결리스트	O(n)	O(n)	O(1)	O(1)	head와 tail을 통해 순회

사실 단방향 연결리스트보다 양방향 연결리스트가 속도는 더 빠르다. 그러나 빅오표기법으로 보게되면 같은 시간복잡도를 가진다.

 

1) 접근

 연결리스트는 인덱스를 가지고 있지 않으므로 특정 엘리먼트에 접근하려고 한다면 Head 또는 Tail로 부터 연결된 링크를 통해 순차적으로 순회하면서 접근할 수 있다. 이 경우 시간 복잡도는 최대 n/2이 걸리지만, 빅오표기법으로 표기한다면 시간복잡도는 O(n).

 

2) 탐색

 탐색도 접근과 마찬가지로 Head 또는 Tail로 부터 순차적으로 연결된 링크를 통해서 순회하면서 탐색할 수 있다. 이 경우 최악의 상황인 경우 시간 복잡도는 O(n).

 

3) 삽입, 삭제

 삽입 이나 삭제 같은 경우 링크만 조정해주면 되기 때문에 시간복잡도는 O(1). 그러나 삽입이나, 삭제를 위해서 탐색이 필요하기 때문에 최종적으로는 O(n)이 필요하다고 봐도 무방. (맨 앞 또는 맨 뒤에 삽입 삭제일 경우에는 O(1) 유지).

 

5. 정리

1. 연결리스트는 배열과 다르게 데이터가 저장될 때 분산되어 저장된다. 이때 각각의 노드들은 다음 엘리먼트의 주소값을 가리키고 있어 이를 기반으로 서로 연결된다.

2. 연결리스트는 데이터가 분산되어 저장되어 있기 때문에, 삽입,삭제 시 배열처럼 엘리먼트들을 한 칸씩 움직일 필요가 없기 때문에, 삽입, 삭제 연산 시 배열보다 빠르다.

3. 접근, 탐색 연산을 할 때 O(n)의 시간복잡도가 발생. 삽입,삭제 시에는 노드간에 링크만 새로 연결해주면 되므로, O(1)의 시간복잡도가 발생하지만, 원하는 위치에 엘리먼트를 삽입,삭제를 하기 위해서는 탐색의 과정이 무조건 필요하므로 실질적으로는 O(n)의 시간복잡도가 소요됨.

 

참조

면접을 위한 CS 전공지식 노트

야놀자 테크스쿨 패스트캠퍼스 온라인 강의 - 자료구조/알고리즘