1. 연결 리스트 (Linked list)

등장 배경

이 자료구조가 등장한 배경은 연속적이지 않은 데이터들을 처리하기 위해서 등장하였다.

 

배열의 경우, 선언할 때 기본적으로 크기를 지정하게 되어있다. 컴퓨터는 이 정보를 활용해서 메모리 상에 consecutive하게 정보를 저장한다. 예를 들어 int arr[4](c class)라고 설정한 경우 컴퓨터는 int형 자료형이므로 4byte씩 4개 총 16개의 byte의 메모리를 할당하여 해당 메모리에 정보들이 consecutive하게 저장된다.

포인터 개념으로 이해해보면, 정보가 연속적으로 저장되어있기에 배열의 시작포인터와 자료형만 알면 해당 배열 index에 저장된 정보를 바로 읽을 수 있는 것이다.

 

그런데, 정보를 저장함에 있어 크기를 당장 정할 수 없는 경우도 존재한다. 물론 배열의 크기를 무한정 크게 잡으면 이러한 문제점을 해결할 수 있으나, 매우 비효율적이다. 따라서 정보를 배열처럼 총 데이터의 크기를 기준으로 연속적인 메모리를 미리 할당을 해놓는 방식이 아니라, 불연속적(noncontigious)한 정보를 계속 연결하는 방식으로 처리하는 자료구조가 연결리스트이다.

 

따라서 이러한 측면때문에 배열과 연결리스트는 접근시간, 삽입시간, 지우는 시간의 시간 복잡도가 차이가 나게 된다.

 

	배열(Array)	연결 리스트(Linked list)
접근 시간	O(1)	O(n)
삽입 시간	O(n)	O(1)
제거 시간	O(n)	O(1)

구현 방법

Linked list를 구현하는 방법에는 여러가지 방법이 존재한다.

 

첫번째로는 Directed 여부이다.

연결리스트를 활용해서 각 노드들을 연결해주는 과정에서, 연결되는 방향이 일방향이면 Directed, 양방향이면 non Directed이다. 일반적으로 일방향인 연결 리스트의 경우는 Singular Linked list, 나머지는 Doubly Linked list라고 명명한다.

 

구현 방법은 Node class의 definition에서 차이가 발생하는데, 자세한 내용은 다음과 같다.

// Singular Linked list

public class Node {
    public int data;
    public Node next;
    public Node(int x){
        data = x;
        next = null;
    }
}

// Doubly Linked list

public class Node {
    public int data;
    public Node next;
    public Node prev;
    public Node(int x){
        data = x;
        next = null;
        prev = null;
    }
}

위 코드의 구현에서 볼 수 있는 것처럼, 두 구현 방식의 차이는 근본적으로 Node class의 정의에서 앞 뒤 노드의 주소에 대한 정보를 가지고 있는지 여부이다. 해당 노드에 대한 주소값을 가지고 있으면 이동할 수 있기 때문이다.

 

일반적으로는 Doubly Linked list가 활용폭이 조금 더 넓다. 해당 이유는 다음과 같다.

연결 리스트에서 어떤 노드를 삭제 해야할 경우를 상정해보자. 그러면, 삭제하기 위해서 필요한 작업은 해당 노드를 기준으로 이전의 노드와 이후의 노드를 서로 연결시켜주는 것이다. 따라서 이 작업을 쉽게 수행되기 위해서는 해당 노드를 기준으로 앞, 뒤 노드에 대한 정보를 가지고 있는 것이 좋다. 이러한 측면에서 Doubly Linked list가 선호되는 편이다.

 

두번째로는 Circular 여부이다.

Linked list는 크게보면 선형과 원형으로 구성될 수 있다.

쉽게 설명하자면, 선형의 경우에는 시작점이 있고 끝 점이 분명하게 존재하고 원형의 경우에는 선형의 상황에서 끝점이 다시 시작점과 연결되는 모양이라고 생각하면 된다.

 

일반적으로 선형인 연결리스트를 Linear Linked list, 원형인 연결리스트를 Circular Linked list라고 부른다.

구현 방법은 Linked list를 관리하는 일종의 Controller의 구현에서 차이가 발생하게 된다.

아래의 코드는 Doubly를 기준으로 살펴보도록 하자. (첫번째 이유에서 설명한 것처럼, Doubly로 구현하는 것이 훨씬 더 쉽고 직관적이다.)

// Linear Linked list

public class linearLinkedList{
    public Node head; // 연결 리스트의 가장 앞의 object를 지시
    public Node tail; // 연결 리스트의 가장 뒤의 object를 지시
    public int size;
    
    public linearLinkedList(){
        size = 0;
        head = null;
        tail = null;
    } // Constructor

    public boolean empty(){
        return (size == 0);
    }

    public void addNodeFront(int x){
        Node newnode = new Node(x); // newnode.data를 x로 초기화
        newnode.prev = null; // 맨 앞에 추가하는 상황이므로 prev는 존재하지 않음
        newnode.next = head; // head가 null 유무와는 관계 없음

        // 기본적으로는 추가된 노드와 head노드와 연결시켜주는 것이 맞음
        // 다만, 기존에 사이즈가 0이었을 경우에는 추가만 시켜주고, head와 tail만 변경
        if(size == 0){
            head = newnode;
            tail = newnode;
        }
        else{
            head.prev = newnode; // 서로 연결시켜주는 작업
            head = newnode; // 결과적으로 head가 바뀐 상황
        }
        size++; // 사이즈 추가
    }

    public void addNodeBack(int x){
        Node newnode = new Node(x); // newnode.data를 x로 초기화
        newnode.next = null; // 맨 앞에 추가하는 상황이므로 prev는 존재하지 않음
        newnode.prev = tail; // tail이 null 유무와는 관계 없음

        // 기본적으로는 추가된 노드와 tail노드와 연결시켜주는 것이 맞음
        // 다만, 기존에 사이즈가 0이었을 경우에는 추가만 시켜주고, head와 tail만 변경
        if(size == 0){
            head = newnode;
            tail = newnode;
        }
        else{
            tail.next = newnode; // 서로 연결시켜주는 작업
            tail = newnode; // 결과적으로 tail이 바뀐 상황
        }
        size++; // 사이즈 추가
    }

    public int deleteNodeFront(){
        if(head == null) return -1; // 지울게 없는 상황
        else{
            int val = head.data; // 지워지는 데이터 값
            
            // 기본적으로는 head 이후의 prev값을 지워주는 작업이 필요함
            // 다만, 기존에 사이즈가 1이였을 경우에는 null포인터이기 때문에 head, tail 변경만 해줌
            if(size == 1){
                head = null;
                tail = null;
            }
            else{
                head.next.prev = null; // 연결상태를 끊어줌
                head = head.next; // 기존 head 노드를 지웠으므로 head 노드 갱신
            }
            size--; // 지웠으므로 사이즈 1개 지움
            return val;
        }
    }

    public int deleteNodeBack(){
        if(tail == null) return -1; // 지울게 없는 상황
        else{
            int val = tail.data; // 지워지는 데이터 값

            // 기본적으로는 tail 이전의 next값을 지워주는 작업이 필요함
            // 다만, 기존에 사이즈가 1이였을 경우에는 null포인터이기 때문에 head, tail 변경만 해줌
            if(size == 1){
                head = null;
                tail = null;
            }
            else{
                tail.prev.next = null; // 연결상태를 끊어줌
                tail = tail.prev; // 기존 tail 노드를 지웠으므로 tail 노드 갱신
            }
            size--; // 지웠으므로 사이즈 1개 지움
            return val;
        }
    }
}

 

// Circular Linked list

public class circularLinkedList {
    public final Node header; // 빈 header Node를 하나 생성
    public int size;

    public circularLinkedList(){
        Node newnode = new Node(-1);
        newnode.next = newnode; // 전부 자기 자신으로 돌아오게끔
        newnode.prev = newnode; // 전부 자기 자신으로 돌아오게끔
        header = newnode;
        size = 0;
    }

    public boolean empty(){
        return (size == 0);
    }

    public void addNodeFront(int x){
        Node newnode = new Node(x);
        newnode.prev = header;
        newnode.next = header.next; // 기존에 element가 없어도 자연스럽게 header와 Circular 형성
        header.next.prev = newnode;
        header.next = newnode;
        size++;
    }

    public void addNodeBack(int x){
        Node newnode = new Node(x);
        newnode.next = header;
        newnode.prev = header.prev; // 기존에 element가 없어도 자연스럽게 header와 Circular 형성
        header.prev.next = newnode;
        header.prev = newnode;
        size++;
    }

    public int deleteNodeFront(){
        if(size == 0) return -1; // 지울게 없는 경우
        else{
            int val;
            Node eraseNode = header.next; 
            val = eraseNode.data;
            eraseNode.next.prev = header;
            header.next = eraseNode.next;
            return val;
        }
    }

    public int deleteNodeBack(){
        if(size == 0) return -1; // 지울게 없는 경우
        else{
            int val;
            Node eraseNode = header.prev; 
            val = eraseNode.data;
            eraseNode.prev.next = header;
            header.prev = eraseNode.prev;
            return val;
        }
    }
}

활용도 측면에서는 Circular Linked list가 높은 편인데, 왜냐하면 header node를 넣고 앞/뒤를 연결시킴으로써 null handling exception을 크게 고려하지 않아도 되기 때문이다.

 

추가적으로 Iterator를 넣어서 처리하는 방법도 존재하기는 하는데, Linked list class에 getIter method를 추가해주면 된다.

기본적으로 위의 내용과 크게 다르지 않으므로 생략하겠다.

(참고 : 자료구조 2차과제 1번)