1. 연결 리스트

연결리스트의 기본 특징

• 리스트의 데이터를 저장하는 노드(Node)들이 사슬의 형태로 연결된 리스트
• 저장할 데이터의 개수는 리스트 초기화 시점에 바로 결정되지 않음(동적 할당)
• 데이터 삽입/삭제 - $O(1)$
  : 데이터 접근에 걸리는 시간을 제외할 경우,
  해당 데이터의 삽입/삭제 자체는 주변 노드의 연결 대상을 변경하는 작업만 수행하기 때문
• 데이터 접근/탐색 - $O(n)$
  : 데이터 탐색/접근 시 항상 리스트의 처음이나 끝에서 시작하기 때문에,
  저장해야 하는 데이터의 개수가 많을수록 접근성이 하락

연결리스트의 종류

단순 연결 리스트(Simply Linked List)

• 각각의 노드가 다음 노드를 단방향으로 가리키는 구조를 갖춘 연결 리스트
• 이동방향이 단방향이기 때문에 다음 노드로의 접근은 쉽지만 이전 노드로의 접근은 어려움

이중 연결 리스트(Doubly Linked List)

• 각각의 노드가 그 이전 노드와 다음 노드를 모두 가리키는 구조를 갖춘 연결 리스트
• 이동방향이 양방향이기 때문에 다음 노드로의 접근과 이전 노드로의 접근이 모두 가능
  : 단순 연결 리스트의 단점을 개선

이중 원형 연결 리스트(Doubly Circular Linked List)

• 마지막 노드가 첫번째 노드를 가리키는 구조의 이중 연결 리스트
  : 마지막 노드의 다음 노드는 첫번째 노드이고, 첫번째 노드의 이전 노드는 마지막 노드
  ex) TV 채널 이동
• 이중 연결 리스트의 접근성을 더욱 개선

---

2. 연결 리스트 구현

• 전체 구현 코드는 여기에서 확인 가능

연결리스트의 공통 기능 정의

LinkedList 인터페이스

package linkedlist;

import java.util.Comparator;

public interface LinkedList<E> {

    boolean isEmpty();          // 빈 리스트인지 확인
    E search(E obj, Comparator<? super E> cmp);     // 인자로 지정한 데이터를 탐색
    void addFirst(E obj);       // 리스트의 맨 앞에 새로운 노드 추가
    void addLast(E obj);        // 리스트의 마지막에 새로운 노드 추가
    E removeFirst();            // 리스트의 첫번째 노드를 제거
    E removeLast();             // 리스트의 마지막 노드를 제거
    void removeCurrentNode();   // 리스트 내 현재 노드를 제거
    
    void clear();       // 리스트의 모든 노드를 제거
    boolean next();     // 현재 노드의 다음 노드로 이동
    void dump();        // 리스트에 저장된 모든 데이터 출력
    int getSize();      // 현재 리스트에 저장된 노드의 개수 반환
}

인터페이스를 사용하여 단순/이중 연결리스트에 공통으로 포함된 핵심 기능을 정의하고,
이를 구현하는 방식으로 단순 연결리스트와 이중 연결리스트를 구현하였음.

단순 연결 리스트 구현

Node1 클래스 구현

package linkedlist;

public class Node1<E> {

    private final E data;       // 데이터 저장
    private Node1<E> next;      // 다음 노드

	// 노드 생성
    Node1(E data, Node1<E> next) {
        this.data = data;
        this.next = next;
    }
    Node1() {
        data = null;
        next = this;
    }

    // 이 노드에 저장된 데이터를 불러옴
    public E getData() {
        return data;
    }

    // 이 노드의 다음 노드를 불러옴
    public Node1<E> getNext() {
        return next;
    }

    // 이 노드의 다음 노드를 지정한 노드로 갱신
    public void setNext(Node1<E> next) {
        this.next = next;
    }
}

SimplyLinkedList 클래스 구현

package linkedlist;

import java.util.Comparator;

public class SimplyLinkedList<E> implements LinkedList<E> {

    private Node1<E> head;      // 연결리스트의 머리 노드를 가리키는 변수
    private Node1<E> current;   // 연결리스트에서 현재 선택한 노드
    private int size;           // 연결리스트에 저장된 노드의 개수

    public SimplyLinkedList() {
        head = current = null;
        size = 0;
    }

    // 현재 가리키는 노드가 없으면 빈 연결리스트로 취급
    @Override
    public boolean isEmpty() {
        return head == null;
    }

    @Override
    public E search(E obj, Comparator<? super E> cmp) {
        // 1. 지정한 데이터를 찾을 때까지 연결 리스트의 머리 노드부터 탐색
        Node1<E> ptr = head;

        while (ptr != null) {
            if (cmp.compare(obj, ptr.getData()) == 0) {
                // 2-1. 탐색 중인 노드가 찾는 노드면 현재 노드를 찾은 노드로 갱신하고, 저장된 데이터를 반환
                current = ptr;
                return ptr.getData();
            }
            // 2-2. 탐색 중인 노드가 찾는 노드가 아니면 다음 노드를 탐색
            ptr = ptr.getNext();
        }
        return null;
    }

    @Override
    public void addFirst(E obj) {
        // 1. 삽입 이전의 머리 노드의 위치를 별도로 저장
        Node1<E> ptr = head;

        // 2. 새로 생성한 현재 노드를 기존의 머리 노드 앞에 연결
        // 3. 머리 노드를 현재 노드로 갱신
        head = current = new Node1<>(obj, ptr);

        // 4. 연결리스트에 저장된 노드의 개수 1 증가
        size++;
    }

    @Override
    public void addLast(E obj) {
        // 1-1. 리스트가 비어 있는 경우 머리에 삽입
        if (isEmpty()) {
            addFirst(obj);
        } else {
            // 1-2. 리스트의 마지막 노드 탐색
            Node1<E> ptr = head;
            while (ptr.getNext() != null) {
                ptr = ptr.getNext();
            }

            // 2. 현재 노드를 새로 생성한 노드로 지정
            current = new Node1<>(obj, null);
            // 3. 탐색된 마지막 노드의 다음 노드에 현재 노드를 연결
            ptr.setNext(current);

            // 4. 연결리스트에 저장된 노드의 개수 1 증가
            size++;
        }
    }

    @Override
    public E removeFirst() {
        if (!isEmpty()) {
            // 1. 빈 연결리스트가 아닌 경우 삭제할 데이터를 별도로 저장
            E data = current.getData();
            // 2. 머리 노드의 바로 다음 노드로 기존의 머리 노드를 갱신하고, 이 노드를 현재 노드로 지정
            head = current = head.getNext();

            // 3. 연결리스트에 저장된 노드의 개수 1 감소
            size--;

            // 4. 삭제한 데이터를 반환
            return data;
        }
        return null;
    }

    @Override
    public E removeLast() {
        if (!isEmpty()) {
            // 1-1. 연결리스트에 저장된 노드가 1개뿐인 경우
            if (head.getNext() == null) {
                removeFirst();
            } else {
                Node1<E> ptr = head;    // 탐색할 노드
                Node1<E> prev = head;   // 탐색할 노드의 직전 노드

                // 1-2. 연결리스트의 마지막 노드까지 이동, 이동 시 마지막 노드와 그 이전 노드를 모두 저장
                while (ptr.getNext() != head) {
                    prev = ptr;
                    ptr = ptr.getNext();
                }

                // 2. 삭제할 데이터를 별도로 저장
                E data = ptr.getData();

                // 3. 연결리스트의 마지막 노드를 삭제한 후 현재 노드를 마지막 노드의 직전 노드로 갱신 
                prev.setNext(null);
                current = prev;
                
                // 4. 연결리스트에 저장된 노드의 개수 1 감소
                size--;
                
                // 5. 삭제된 데이터를 반환
                return data;
            }
        }
        return null;
    }

    private void remove(Node1<E> p) {
        if (!isEmpty()) {
            // 1-1. 삭제할 노드가 머리 노드인 경우
            if (p == head) {
                removeFirst();
            } else {
                // 1-2. 삭제할 노드가 머리 노드가 아닌 경우 연결리스트의 처음부터 탐색
                Node1<E> ptr = head;
                while (ptr.getNext() != p) {
                    ptr = ptr.getNext();
                    
                    // 2-1. 삭제하려는 노드가 연결리스트에 없는 경우 그대로 종료
                    if (ptr == null) {
                        return;
                    }
                }
                // 2-2. 삭제할 노드의 바로 이전 노드를 삭제할 노드의 다음 노드에 직접 연결하여 노드 삭제 
                ptr.setNext(p.getNext());
                
                // 현재 노드를 삭제한 노드의 직전 노드로 갱신
                current = ptr;
                
                // 연결리스트에 저장된 노드의 개수 1 감소
                size--;
            }
        }
    }
    
    @Override
    public void removeCurrentNode() {
        remove(current);
    }

    @Override
    public void clear() {
        // 연결리스트에 저장된 모든 노드를 삭제
        while (!isEmpty()) {
            removeFirst();
        }
        current = null;
        size = 0;
    }

    @Override
    public boolean next() {
        // 현재 선택된 노드가 없거나, 현재 노드가 마지막 노드가 아닌 경우 다음 노드로 이동 불가
        if (current == null || current.getNext() == null) {
            return false;
        }
        current = current.getNext();
        return true;
    }

    @Override
    public void dump() {
        Node1<E> p = head;
        
        // 연결리스트 내 각각의 노드에 저장된 값을 출력 
        while (p != null) {
            System.out.println(p.getData());
            p = p.getNext();
        }
    }

    @Override
    public int getSize() {
        return size;
    }
}

실행 코드 및 실행 결과

package linkedlist;

import java.util.Comparator;

public class SimplyLinkedListMain {

    public static void main(String[] args) {
        SimplyLinkedList<Integer> list = new SimplyLinkedList<>();
        
        // 리스트에 0~9까지의 정수값 저장
        for (int i = 0; i < 10; i++) {
            list.addLast(i);
        }

        // 리스트에 저장된 노드의 개수, 저장된 모든 정수값 출력
        System.out.printf("list size: %d\n", list.getSize());
        list.dump();
        System.out.println();

        // 리스트에서 짝수를 저장한 노드만 삭제
        for (int i = 0; i < 10; i++) {
            if (i % 2 == 0) {
                list.search(i, Comparator.naturalOrder());
                list.removeCurrentNode();
            }
        }
        // 노드 삭제 후 리스트에 저장된 노드 개수, 현재 저장된 정수값을 모두 출력
        System.out.printf("list size: %d\n", list.getSize());
        list.dump();
        System.out.println();

        // 리스트의 모든 노드 삭제 후 결과 출력
        list.clear();
        System.out.printf("list size: %d\n", list.getSize());
    }
}

이중 연결 리스트 구현

Node2 클래스 구현

package linkedlist;

public class Node2<E> {

    private final E data;       // 이 노드에 저장할 데이터
    private Node2<E> prev;      // 이 노드의 이전 노드
    private Node2<E> next;      // 이 노드의 다음 노드

    // 노드 생성
    Node2() {
        data = null;
        prev = next = this;
    }
    Node2(E obj, Node2<E> prev, Node2<E> next) {
        this.data = obj;
        this.prev = prev;
        this.next = next;
    }

    // 이 노드에 저장된 데이터 불러오기
    public E getData() {
        return data;
    }

    // 이 노드의 다음 노드 불러오기
    public Node2<E> getNext() {
        return next;
    }

    // 이 노드의 다음 노드를 지정한 노드로 변경
    public void setNext(Node2<E> next) {
        this.next = next;
    }

    // 이 노드의 이전 노드 불러오기
    public Node2<E> getPrev() {
        return prev;
    }

    // 이 노드의 이전 노드를 지정한 노드로 변경
    public void setPrev(Node2<E> prev) {
        this.prev = prev;
    }
}

DoublyLinkedList 클래스 구현

DoublyLinkedList 구현 코드에서 변경된 내용

• 한 노드에서 다음 노드와 이전 노드의 탐색이 모두 가능
• 머리 노드로 더미 노드를 사용
  : 노드의 위치에 관계없이 노드의 추가/삭제를 일관적으로 수행 가능
• 원형 이중 연결리스트로 구현
  : 머리 노드의 다음 노드는 리스트의 첫번째 노드, 머리 노드의 이전 노드는 리스트의 마지막 노드

DoublyLinkedList 구현 코드에서 새로 추가한 메서드

private void add(E obj)

• (현재 노드)-(다음 노드)에 새로운 노드 추가 시
  (현재 노드)-(새로운 노드)-(다음 노드)로 연결을 재설정
• 새로운 노드 추가 기능에 관한 핵심 코드

public void addFirst(E obj) / public void addLast(E obj)

• 현재 노드로 리스트의 첫번째 노드와 마지막 노드 중 하나를 선택한다는 차이가 존재하나,
  핵심 로직은 add() 메서드를 활용한다는 점에서 동일

public void removeCurrentNode()

• (이전 노드)-(현재 노드)-(다음 노드)에서 현재 노드 삭제 시
  (이전 노드)-(다음 노드)로 노드 간 연결을 재설정
• 노드 삭제에 관한 핵심 코드

public E removeFirst() / public E removeLast()

• 현재 노드를 리스트의 첫번째 노드나 마지막 노드로 변경한 후 removeCurrentNode()를 실행하는 방식으로 구현

public boolean prev()

• 한 노드에서 이전 노드로의 접근이 가능하므로 next() 메서드의 코드를 일부 변형하여 구현

public void dumpReverse()

• 리스트의 마지막 노드부터 접근하는 방식으로 리스트의 노드를 연결 순서의 역순으로 탐색하여 저장된 데이터를 출력

DoublyLinkedList 구현 코드

package linkedlist;

import java.util.Comparator;

public class DoublyLinkedList<E> implements LinkedList<E> {

    private final Node2<E> head;    // 머리 노드를 가리키는 변수
    private Node2<E> current;       //
    private int size;

    // 원형 이중 연결 리스트 생성: 머리 노드는 항상 더미 노드
    // 더미 노드 사용 시 머리 노드는 항상 고정
    public DoublyLinkedList() {
        head = current = new Node2<>();
        size = 0;
    }

    // 리스트에 더미 노드만 존재하면 빈 리스트로 취급
    @Override
    public boolean isEmpty() {
        return head.getNext() == head;
    }

    // 지정한 데이터를 갖는 노드를 찾아 현재 노드로 지정한 후 데이터 반환
    @Override
    public E search(E obj, Comparator<? super E> cmp) {
        Node2<E> ptr = head.getNext();  // 첫 노드는 더미 노드의 다음 노드

        while (ptr != head) {
            if (cmp.compare(obj, ptr.getData()) == 0) {
                current = ptr;
                return ptr.getData();
            }
            ptr = ptr.getNext();
        }
        return null;
    }

    public void add(E obj) {
        // 1. 새로운 노드 생성
        Node2<E> node2 = new Node2<>(obj, current, current.getNext());

        // 2. 새로운 노드를 현재 노드와 현재 노드의 바로 다음 노드 사이에 삽입
        current.getNext().setPrev(node2);
        current.setNext(current.getNext().getPrev());

        // 3. 현재 노드를 새로 생성한 노드로 변경
        current = node2;

        // 4. 리스트에 저장된 노드의 개수 1 증가
        size++;
    }

    @Override
    public void addFirst(E obj) {
        // 현재 노드를 머리 노드(더미 노드)로 갱신한 후 새로운 노드를 그 다음 노드로 저장
        current = head;
        add(obj);
    }

    @Override
    public void addLast(E obj) {
        // 현재 노드를 마지막 노드로 갱신한 후 새로운 노드를 그 다음 노드로 저장
        // 원형 연결리스트이므로 머리 노드의 직전 노드 = 리스트의 마지막 노드
        current = head.getPrev();
        add(obj);
    }

    @Override
    public void removeCurrentNode() {
        if (!isEmpty()) {
            // 1. 현재 노드의 직전 노드와 직후 노드를 서로 연결하여 현재 노드를 리스트에서 제거
            current.getPrev().setNext(current.getNext());
            current.getNext().setPrev(current.getPrev());

            // 2. 현재 노드는 현재 노드의 직전 노드로 갱신
            current = current.getPrev();

            // 3. 현재 노드가 더미 노드인 경우 현재 노드가 리스트의 첫번째 노드를 가리키도록 조정
            // (연속 삭제 시 리스트의 첫번째 노드 삭제를 원활히 수행하기 위한 추가 작업)
            if (current == head) {
                current = head.getNext();
            }

            // 4. 리스트에 저장된 노드의 개수 1 감소
            size--;
        }
    }

    public void remove(Node2<E> p) {
        Node2<E> ptr = head.getNext();  // 리스트의 첫번째 노드부터 시작

        // 리스트 내부에서 지정한 노드를 찾아 삭제
        while (ptr != head) {
            if (ptr == p) {
                current = p;
                removeCurrentNode();
                break;
            }
            // 탐색 중인 노드가 지정한 노드가 아니면 다음 노드 탐색
            ptr = ptr.getNext();
        }
    }

    @Override
    public E removeFirst() {
        // 1. 현재 노드를 리스트의 첫번째 노드로 변경
        current = head.getNext();

        // 2. 삭제할 데이터를 별도로 저장
        E data = current.getData();

        // 3. 노드 삭제
        remove(current);

        // 4. 삭제한 데이터 반환
        return data;
    }

    @Override
    public E removeLast() {
        // 1. 현재 노드를 리스트의 마지막 노드로 변경
        current = head.getPrev();

        // 2. 삭제할 데이터를 별도로 저장
        E data = current.getData();

        // 3. 노드 삭제
        remove(current);

        // 4. 삭제한 데이터 반환
        return data;
    }

    @Override
    public void clear() {
        while (!isEmpty()) {
            removeCurrentNode();
        }
    }

    @Override
    public boolean next() {
    	// 리스트가 비어 있거나 이동할 다음 노드가 더 이상 없는 경우 그대로 종료
        if (isEmpty() || current.getNext() == head) {
            return false;
        }
        current = current.getNext();
        return true;
    }
    
    public boolean prev() {
        // 리스트가 비어 있거나 이동할 이전 노드가 더 이상 없는 경우 그대로 종료
        if (isEmpty() || current.getPrev() == head) {
            return false;
        }
        // 이동할 노드가 있을 경우 현재 선택한 노드의 직전 노드로 이동
        current = current.getPrev();
        return true;
    }

    @Override
    public void dump() {
        Node2<E> ptr = head.getNext();

        // 리스트의 데이터를 저장된 순서대로 출력
        while (ptr != head) {
            System.out.println(ptr.getData());
            ptr = ptr.getNext();
        }
    }
    
    public void dumpReverse() {
        Node2<E> ptr = head.getPrev();

        // 리스트의 데이터를 저장된 순서의 역순으로 출력
        while (ptr != head) {
            System.out.println(ptr.getData());
            ptr = ptr.getPrev();
        }
    }

    @Override
    public int getSize() {
        return size;
    }
}

실행 코드 및 실행 결과

package linkedlist;

public class DoublyLinkedListMain {

    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

        // 1. 4~6까지의 정수를 오름차순으로 리스트에 저장
        for (int i = 4; i <= 6; i++) {
            list.addLast(i);
        }
        // 리스트에 저장된 노드 개수 출력
        System.out.printf("list size: %d\n", list.getSize());
        // 리스트에 저장된 정수값을 저장된 순서, 혹은 그 역순으로 출력
        list.dump();
        System.out.println();
        list.dumpReverse();
        System.out.println();

        // 연결리스트의 마지막 노드부터 역순으로 삭제 - 데이터 삭제 순서는 저장 순서의 역순
        while (!list.isEmpty()) {
            System.out.printf("removedData: %d, list size: %d\n", list.removeLast(), list.getSize());
        }
        System.out.println();


        // 2. 4~6까지의 정수가 내림차순이 되도록 리스트에 저장
        for (int i = 4; i <= 6; i++) {
            list.addFirst(i);
        }

        System.out.printf("list size: %d\n", list.getSize());
        list.dump();
        System.out.println();
        list.dumpReverse();
        System.out.println();

        // 연결리스트의 첫번째 노드부터 삭제 - 데이터 삭제 순서는 저장 순서와 일치
        while (!list.isEmpty()) {
            System.out.printf("removedData: %d, list size: %d\n", list.removeFirst(), list.getSize());
        }
    }
}

---

Reference

• Do-it! 자료구조와 함께 배우는 알고리즘 입문(Bohyoh Shibata 지음, 강민 옮김)
• 윤성우의 열혈 자료구조(윤성우 지음)