연결 리스트

연결 리스트란?

배열과 다르게 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조이며, 각 노드는 포인터를 이용해 서로를 연결하여 접근한다.

연결리스트 특징

장점

1. 배열과 다르게 요소의 수만큼 메모리를 할당받을 필요가 없다.
2. 배열과 다르게 공간을 추가로 할당받거나 나머지 데이터들의 위치를 이동시킬 필요가 없어서 삽입 및 삭제가 용이하다.

 

단점

1. 배열과 다르게 특정 인덱스의 위치에 O(1)에 접근하지 못하고 앞에서부터 순차적으로 요소를 탐색해야한다.
2. 각 노드가 데이터만 가지고 있는 것이 아닌, 포인터 변수의 공간도 추가적으로 필요하다.

코드로 보는 연결 리스트

노드 구현

class Node {
    private Node left;
    private Node right;
    private final int data;

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

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public int getData() {
        return data;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

1. 노드 클래스는 왼쪽 노드와 오른쪽 노드를 가리키고 있는 참조 변수와 보관할 데이터 변수를 가지고 있다. 

연결리스트 구현

class LinkedList {
    private Node head;
    private Node tail;

...
}

1. 연결리스트는 맨 처음 노드를 가리키는 head와 마지막 노드를 가리키는 tail을 가지고 있다.
2. 맨 처음 아무런 노드가 존재하지 않을 때는 head와 tail이 null을 가리키게 된다.

연결리스트에 노드 추가 구현

    public void addFirst(int data) {
        Node node = new Node(data);
        if(isEmpty()) {
            head = tail = node;
        }
        else {
            node.setRight(head);
            head.setLeft(node);
            head = node;
        }
    }

    public void addLast(int data) {
        Node node = new Node(data);
        if(isEmpty()) {
            head = tail = node;
        }
        else {
            tail.setRight(node);
            node.setLeft(tail);
            tail = node;
        }
    }

1. 각각 맨 앞에 새로운 node를 넣는 메서드와 맨 뒤에 새로운 node를 넣는 메서드이다.
2. 만약 LinkedList가 비어있다면 head와 tail에 새로운 node를 가리키도록 변수들을 초기화 해야한다. 
3. 만약 LinkedList가 비어 있지 않다면, head에 있는 node를 새로운 node의 오른쪽에 위치하도록 참조 변수들을 조정한 후 기존 head에 새로운 node를 연결시켜준다. 

연결리스트에 노드 제거 구현

    public void remove(int data) {
        Node node = head;
        while(node != null) {
            if(node.getData() == data) {
                if(node == head) {
                    if(node.getRight() != null) {
                        head = node.getRight();
                        node.getRight().setLeft(null);
                    }
                    else {
                        head = tail = null;
                    }
                }
                else if(node == tail){
                    tail = node.getLeft();
                    node.getLeft().setRight(null);
                }
                else {
                    node.getLeft().setRight(node.getRight());
                    node.getRight().setLeft(node.getLeft());
                }

                node = null;
                break;
            }

            node = node.getRight();
        }
    }

1. head와 tail을 더미 노드로 사용하지 않고 실제 노드로 사용하여 remove 메서드가 굉장히 길어졌다.
2. head와 tail이 데이터를 담고 있는 의미 있는 노드이므로, 삭제할 때 아래와 같이 많은 조건을 확인해야 한다.   

 

첫번째. 삭제할 노드가 head인가? 

두번째. 삭제할 노드가 tail인가? 

세번째. 삭제할 노드가 head, tail도 아닌 일반 노드인가? 

 

위의 조건에 따라 구현 해야하는 로직이 달라진다.

첫번째 조건의 경우 head의 오른쪽에 있는 노드를 head로 연결시켜줘야 한다. 또 만약에 LinkedList에 head 노드 밖에 없는 상황이라면 head를 단순히 null로 초기화한다. 

두번째 조건의 경우 tail을 삭제할 노드의 왼쪽으로 연결시켜줘야 한다. 이미 head에서 데이터가 하나밖에 없는 경우(head==tail)를 체크해줬기 때문에 다른 부분은 신경써줄 필요가 없다. 

세번째 조건인 경우 삭제할 노드의 양쪽 노드를 서로 연결시켜주면 된다. 

 

만약 head와 tail을 더미노드로 사용한다면 단순히 세번째 조건만 구현하면 된다. 

 

연결리스트 전체 코드

class Node {
    private Node left;
    private Node right;
    private final int data;

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

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public int getData() {
        return data;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

class LinkedList {
    private Node head;
    private Node tail;

    public LinkedList() {
        head = null;
        tail = null;
    }

    public void addFirst(int data) {
        Node node = new Node(data);
        if(isEmpty()) {
            head = tail = node;
        }
        else {
            node.setRight(head);
            head.setLeft(node);
            head = node;
        }
    }

    public void addLast(int data) {
        Node node = new Node(data);
        if(isEmpty()) {
            head = tail = node;
        }
        else {
            tail.setRight(node);
            node.setLeft(tail);
            tail = node;
        }
    }

    public void remove(int data) {
        Node node = head;
        while(node != null) {
            if(node.getData() == data) {
                if(node == head) {
                    if(node.getRight() != null) {
                        head = node.getRight();
                        node.getRight().setLeft(null);
                    }
                    else {
                        head = tail = null;
                    }
                }
                else if(node == tail){
                    tail = node.getLeft();
                    node.getLeft().setRight(null);
                }
                else {
                    node.getLeft().setRight(node.getRight());
                    node.getRight().setLeft(node.getLeft());
                }

                node = null;
                break;
            }

            node = node.getRight();
        }
    }

    public boolean isEmpty() {
        return head == null;
    }
 }