연결 리스트

연결리스트

• 데이터를 링크로 연결해서 관리하는 구조
• 자료의 순서는 정해져 있지만, 메모리상 연속성은 보장되지 않음

연결 리스트의 장점

• 데이터 공간을 미리 할당할 필요가 없음
• 리스트의 길이가 가변적이라 추가/삭제에 용이

연결 리스트의 단점

• 연결 구조를 위한 별도 데이터 공간 필요
• 연결 정보를 찾는 시간이 필요 (접근 속도가 상대적으로 느림)
• 데이터 추가, 삭제 시 앞 뒤 데이터의 연결을 재구성하는 작업 필요

 

 

배열과 연결 리스트의 시간 복잡도는 위와 같습니다.

 

연결 리스트의 종류

• 단순 연결 리스트
• 양방향 연결 리스트
• 원형 연결 리스트

 

단순 연결 리스트 구현

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 (head == null) {
            return true;
        }

        return false;
    }

    //  연결 리스트의 맨 뒤에 데이터 추가
    public void addData(int data) {
        if (head == null) {
            head = new Node(data, null);
            return;
        }

        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }

        cur.next = new Node(data, null);
    }


    //  연결 리스트의 맨 뒤의 데이터 삭제
    public void removeData() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = head;
        Node prev = cur;
        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }

        if (cur == head) {
            head = null;
            return;
        }

        prev.next = null;
    }


    //  연결 리스트에서 데이터 찾기
    public void findData(int data) {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = head;

        while (cur.next != null) {
            if (cur.data == data) {
                System.out.println("Data exist!");
                return;
            }
            cur = cur.next;
        }
        System.out.println("Data not found!");
    }


    //  연결 리스트의 모든 데이터 출력
    public void showData() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

 

단순 연결 리스트 중간에서 값 추가/삭제

public void addData(int data, Integer beforeData) {
    if (head == null) {
        head = new Node(data, null);
        return;
    }

    if (beforeData == null) {
        Node cur = head;
        while (cur != null) {
            cur = cur.next;
        }

        cur.next = new Node(data, null);
        return;
    }

    Node cur = head;
    Node prev = cur;
    while (cur != null) {
        if (cur.data == beforeData) {
            if (cur == head) {
                head = new Node(data, head);
            } else {
                prev.next = new Node(data, cur);
            }
            break;
        }
        prev = cur;
        cur = cur.next;
    }
}

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

    Node cur = head;
    Node prev = cur;
    while (cur != null) {
        if (cur.data == data) {
            if (cur == head) {
                head = cur.next;
                return;
            }

            prev.next = cur.next;
            break;
        }
        prev = cur;
        cur = cur.next;
    }
}

양방향 연결 리스트

class Node {
    int data;
    Node next;
    Node prev;

    Node() { }

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

class DoublyLinkedList {
    Node head;
    Node tail;

    DoublyLinkedList() { }

    DoublyLinkedList(Node 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 (head == null) {
            head = new Node(data, null, null);
            tail = head;
            return;
        }

        if (beforeData == null) {
            tail.next = new Node(data, null, tail);
            tail = tail.next;
            return;
        }

        Node cur = head;
        Node prev = cur;
        while (cur != null) {
            if (cur.data == beforeData) {
                if (cur == head) {
                    head = new Node(data, head, null);
                    head.next.prev = head;
                    return;
                }

                prev.next = new Node(data, cur, prev);
                cur.prev = prev.next;
                break;
            }
            prev = cur;
            cur = cur.next;
        }
    }

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

        Node cur = head;
        Node prev = cur;
        while (cur != null) {
            if (cur.data == data) {
                if (cur == head && cur == tail) {
                    this.head = null;
                    this.tail = null;
                    return;
                }

                if (cur == head) {
                    head.next = cur.next;
                    head.prev = null;
                    return;
                }

                if (cur == tail) {
                    tail = tail.prev;
                    tail.next = null;
                    return;
                }

                prev.next = cur.next;
                cur.next.prev = prev;
                break;
            }
            prev = cur;
            cur = cur.next;
        }
    }

    public void showData() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = head;

        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void showDataFromTail() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = tail;

        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.prev;
        }
        System.out.println();
    }
}

원형 연결 리스트

class Node {
    int data;
    Node next;
    Node prev;

    Node() { }

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

class CircularLinkedList {
    Node head;
    Node tail;

    CircularLinkedList() { }

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

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

        return false;
    }

    // 연결 리스트에 데이터 추가
    // before_data 가 null 인 경우, 가장 뒤에 추가
    // before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
    public void addData(int data, Integer beforeData) {
        if (head == null) {
            head = new Node(data, null, null);
            tail = head;
            head.next = head;
            head.prev = head;
            return;
        }

        if (beforeData == null) {
            tail.next = new Node(data, head, tail);
            head.prev = tail.next;
            tail = tail.next;
            return;
        }

        Node cur = head;
        Node prev = cur;
        do {
            if (beforeData == cur.data) {
                if (cur == head) {
                    head = new Node(data, head, tail);
                    tail.next = head;
                    head.prev = head;
                    return;
                }

                prev.next = new Node(data, cur, prev);
                cur.prev = prev.next;
            }

            prev = cur;
            cur = cur.next;
        } while (cur != head);
    }

    //  연결 리스트에서 특정 값을 가진 노드 삭제
    public void removeData(int data) {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = head;
        Node prev = cur;
        while (cur != null) {
            if (data == cur.data) {
                if (cur == head && cur == tail) {
                    this.head = null;
                    this.tail = null;
                    return;
                }

                if (cur == head) {
                    cur.next.prev = head.prev;
                    tail.next = cur.next;
                    head = cur.next;
                    return;
                }

                if (cur == tail) {
                    prev.next = cur.next;
                    tail = prev;
                    head.prev = tail;
                    return;
                }

                prev.next = cur.next;
                cur.next.prev = prev;
                break;
            }

            prev = cur;
            cur = cur.next;
        }
    }

    public void showData() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = head;
        while(cur.next != head) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println(cur.data);
    }
}