[선형 자료구조] 연결리스트(Linked List)

연결리스트는 데이터를 링크로 연결해서 관리하는 자료구조다. 자료의 순서는 정해져 있지만 메모리상의 연속성은 보장되지 않는다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다.

 

연결리스트 구조

 

연결리스트에서 사용되는 용어는 다음과 같다.

node : 데이터 저장 단위로 값과 포인터로 구성된다.(내부 부품이기에 외부에 노출되지 않는것이 좋다. private)

pointer : 다음 노드나 이전 노드의 연결 정보(다음 혹은 이전 노드의 주소(정보)값)(Next)

head : 가장 처음에 위치하는 노드를 일컫는다.

tail : 가장 마지막에 위치하는 노드를 일컫는다.

노드를 가리키는 포인터는 C에서는 포인터변수가 있었지만 여기서는 그냥 같은 타입으로 해서 연결해주면 된다. node.next=new node()// next에 해당하는 노드

 

연결리스트 장점

데이터 공간을 미리 할당할 필요 없다, 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이하다.(구현 관점에서가 아닌 데이터 관리 측면에서 용이하다는 뜻)

 

연결리스트 단점

연결구조를 위한 별도 데이터 공간 필요하다.

특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어진다. 즉, 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것을 권장한다. (자바 LinkedList의 경우 인덱스를 사용하여 연산을 수행할 수 있도록 get(index) 형태의 메서드를 제공하지만, 메서드 내부의 동작은 순차 탐색으로 이루어져 있다) 또한 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 (코딩 관점에서) 필요해진다.

 

연결리스트 시간복잡도 ( Big O )

• 추가(Add) - O(1)
• 삭제(Remove) - O(1)
• 탐색(Search) O(n)
• 접근(access) - O(n)

** 추가, 삭제에 탐색을 포함하면 O(n)이 된다. **

기본 연산으로는 추가, 삭제 등이 있다.

 

연결리스트 종류

1) 단방향(단일) 연결 리스트(Singly Linked List)

Singly Linked List

단방향은 보통 head만 있다. 각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트이다.
일반적으로 큐를 구현할 때 사용된다.
Head 노드를 잃어버려 참조하지 못하는 경우 데이터 전체를 사용 못하게 되는 단점이 있다.

데이터 추가, 삭제는 위치(head, 중간, tail)에 따라 다른 연결 작업이 필요하다.

 

데이터 추가(head)

1. 추가할 데이터를 담은 새로운 노드 생성

2. 새로운 노드를 기존 head에 연결

3. head가 새로운 노드를 가리키도록 변경

 

데이터 추가(tail)

1. 추가할 데이터를 담은 새로운 노드 생성

2. head로부터 끝 노드까지 순회

3. 끝 노드를 추가한 새로운 노드에 연결(연결작업)

 

데이터 추가(중간)

1. 추가할 데이터를 담은 새로운 노드 생성

2. head로부터 추가위치 직전까지 순회

3. 새로운 노드를 다음 노드에 연결

4. 전 노드를 새로운 노드에 연결

** 4, 3 순서로 연결하면 data2를 가리키던 정보가 유실된다. **

 

데이터 삭제(head)

1. head를 삭제 대상 노드로 지정(delete_node)

2. head를 다음 노드로 이전

3. delete_node 삭제

** 이게 일반적인 연결리스트 작업과정인데 자바는 GC가 있기 때문에 head만 이전해줘도 되는듯하다. **

 

데이터 삭제(tail)

1. head로부터 끝 노드까지 순회

2. 끝 노드 삭제

3. 삭제 이전 노드의 링크처리

자바는 링크처리까지만 해줘도 되는듯하다.

 

데이터 삭제(중간)

1. 삭제 대상 노드까지 순회 및 해당 노드 지정(delete_node)

2. 삭제 대상 이전/이후 노드 연결작업

3. delete_node 삭제(자바 불필요)

 

직접구현(java)

class Node {
    int data;
    Node next; // 포인터

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

class LinkedList {
    Node head;
    LinkedList() {}
    LinkedList(Node node) {
        this.head = node;
    }
    public boolean isEmpty() { // 빈 연결리스트인지 확인
        if (this.head == null) {
            return true;
        }
        return false;
    }

    // beforeData 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
    public void addData(int data, Integer beforeData) {
        if (this.isEmpty()) { // 빈 연결리스트일 경우
            this.head = new Node(data, null);
        } else if (beforeData == null) { // 끝 추가
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(data, null);
        } else {
            Node cur = this.head;
            Node pre = cur;
            while (cur != null) {
                if (cur.data == beforeData) {
                    if (cur == this.head) { // head 추가
                        this.head = new Node(data, this.head);
                    } else { // 중간 추가
                        pre.next = new Node(data, cur);
                    }
                    break;
                }
                pre = cur;
                cur = cur.next;
            }
        }
    }

    public void removeData(int data) {
        if (this.isEmpty()) { // 빈 연결리스트일 경우
            System.out.println("List is empty");
            return;
        }

        Node cur = this.head;
        Node pre = cur;
        while (cur != null) {
            if (cur.data == data) {
                if (cur == this.head) { // 첫 제거
                    this.head = cur.next;
                } else { // 중간, 끝 제거
                    pre.next = cur.next;
                }
                break;
            }

            pre = cur;
            cur = cur.next;
        }
    }
}

2) 양방향(이중) 연결 리스트(Doubly Linked List)

Doubly Linked List

각 노드가 이전 노드, 다음 노드에 대해서 참조하는 형태의 연결 리스트이다.
삭제가 간편하며 단일 연결 리스트에 비해 데이터 손상에 강하지만, 관리할 참조가 2개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많아지게 된다.

단일 연결 리스트처럼 데이터 추가, 삭제위치(head, 중간, tail)에 따라 조금씩 다른 작업이 필요하다. 단일 연결 리스트처럼 만들지만, prev까지 고려해서 만들어주면 된다. tail 제거의 경우, head부터 순회할 필요없이 tail로 보면 된다.

 

직접구현(java)

class NodeBi {
    int data;
    NodeBi next;
    NodeBi prev;

    NodeBi(int data, NodeBi next, NodeBi prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

class DoublyLinkedList{
    NodeBi head;
    NodeBi tail;

    DoublyLinkedList(NodeBi node) {
        this.head = node;
        this.tail = node;
    }

    public boolean isEmpty() {
        if (this.head == null) {
            return true;
        }
        return false;
    }

    public void addData(int data, Integer beforeData) {
        if (this.head == null) { // 빈 연결리스트일 경우
            this.head = new NodeBi(data, null, null);
            this.tail = this.head;
        } else if (beforeData == null) { // 끝 추가
            this.tail.next = new NodeBi(data, null, this.tail);
            this.tail = this.tail.next;
        } else {
            NodeBi cur = this.head;
            NodeBi pre = cur;
            while (cur != null) {
                if (cur.data == beforeData) {
                    if (cur == this.head) { // head 추가
                        this.head = new NodeBi(data, this.head, null);
                        this.head.next.prev = this.head;
                    } else { // 중간 추가
                        pre.next = new NodeBi(data, cur, pre);
                        cur.prev = pre.next;
                    }
                    break;
                }
                pre = cur;
                cur = cur.next;
            }
        }
    }

    public void removeData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        NodeBi cur = this.head;
        NodeBi pre = cur;

        while (cur != null) {
            if (cur.data == data) {
                if (cur == this.head && cur == this.tail) { // 노드가 하나일 때
                    this.head = null;
                    this.tail = null;
                } else if (cur == this.head) { // 첫 제거
                    this.head = cur.next;
                    this.head.prev = null;
                } else if (cur == this.tail) { // 끝 제거
                    this.tail = this.tail.prev;
                    this.tail.next = null;
                } else { // 중간 제거
                    pre.next = cur.next;
                    cur.next.prev = pre;
                }
                break;
            }

            pre = cur;
            cur = cur.next;
        }
    }
}

3) 원형 연결 리스트(Circular Linked List)

Circular Linked List

연결 리스트에서 마지막 요소가 첫번째 요소를 참조한다. 단일 원형 연결 리스트도 있고, 이중 원형 연결 리스트도 있다.
스트림 버퍼의 구현에 많이 사용된다. tail의 next는 head, head의 prev는 tail임을 잘 생각하면서 사용하면 된다.

 

직접구현(이중 원형 연결 리스트, java)

class NodeBi {
    int data;
    NodeBi next;
    NodeBi prev;

    NodeBi(int data, NodeBi next, NodeBi prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

class CircularLinkedList {
    NodeBi head;
    NodeBi tail;

    CircularLinkedList(NodeBi node) {
        this.head = node;
        this.tail = node;
        node.next = this.head;
        node.prev = this.head;
    }

    public boolean isEmpty() {
        if (this.head == null) {
            return true;
        }
        return false;
    }

    public void addData(int data, Integer beforeData) {
        if (this.head == null) { // 빈 연결리스트일 경우
            NodeBi newNodeBi = new NodeBi(data, null, null);
            this.head = newNodeBi;
            this.tail = newNodeBi;
            newNodeBi.next = newNodeBi;
            newNodeBi.prev = newNodeBi;
        } else if (beforeData == null) { // 끝 추가
            NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
            this.tail.next= newNodeBi;
            this.head.prev = newNodeBi;
            this.tail = newNodeBi;
        } else {
            NodeBi cur = this.head;
            NodeBi pre = cur;
            do {
                if (cur.data == beforeData) {
                    if (cur == this.head) { // 첫 추가
                        NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
                        this.tail.next = newNodeBi;
                        this.head.prev = newNodeBi;
                        this.head = newNodeBi;
                    } else { // 중간 추가
                        NodeBi newNodeBi = new NodeBi(data, cur, pre);
                        pre.next = newNodeBi;
                        cur.prev = newNodeBi;
                    }
                    break;
                }
                pre = cur;
                cur = cur.next;
            } while (cur != this.head);
        }
    }

    public void removeData(int data) {
        if (this.isEmpty()) { // 빈 연결리스트일 경우
            System.out.println("List is empty");
            return;
        }

        NodeBi cur = this.head;
        NodeBi pre = cur;
        while (cur != null) {
            if (cur.data == data) { 
                if (cur == this.head && cur == this.tail) { // 노드가 하나일 경우
                    this.head = null;
                    this.tail = null;
                } else if (cur == this.head) { // 첫 제거
                    cur.next.prev = this.head.prev;
                    this.head = cur.next;
                    this.tail.next = this.head;
                } else if (cur == this.tail) { // 끝 제거
                    pre.next = this.tail.next;
                    this.tail = pre;
                    this.head.prev = this.tail;
                } else { // 중간 제거
                    pre.next = cur.next;
                    cur.next.prev = pre;
                }
                break;
            }

            pre = cur;
            cur = cur.next;
        }
    }
}

자바 LinkedList

java.util.LinkedList에 이미 만들어진 LinkedList가 있으며 내부 메소드를 통해 위 3가지 종류의 연결리스트를 모두 이용할 수 있다.

사용법만 간단하게 알아보자.

LinkedList<Integer> list = new LinkedList<Integer>();

//추가
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가

//제거
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(1); //index 1 제거
list.clear(); //모든 값 제거

list.size(); //list 크기

list.get(0) //0번째 index 출력
ll.set(1, 3); // 1번째 index의 데이터를 3으로 변경

//검색
list.contains(1)); //list에 1이 있는지 검색 : true
list.indexOf(1); //1이 있는 index반환 없으면 -1