6.1 리스트 추상 데이터 타입

리스트의 소개

리스트에는 항목들이 차례대로 저장되어 있다.
리스트의 항목들은 순서 또는 위치를 가진다.
스택과 큐도 넓게 보면 리스트의 일종이다.
기본 연산:

• 리스트에 새로운 항목을 추가한다(삽입 연산)
• 리스트에서 항목을 삭제한다(삭제 연산)
• 리스트에서 특정한 항목을 찾는다(탐색 연산)

리스트 ADT

객체: n개의 element형으로 구성된 순서 있는 모임
연산:
  insert(list, pos, item) ::= pos 위치에 요소를 추가한다.
  insert_last(list, item) ::= 맨 끝에 요소를 추가한다.
  insert_first(list, item) ::= 맨 처음에 요소를 추가한다.
  delete(list, pos) ::= pos 위치의 요소를 제거한다.
  clear(list) ::= 리스트의 모든 요소를 제거한다.
  get_entry(list, pos) ::= pos 위치의 요소를 반환한다.
  get_lenth(list) ::= 리스트의 길이를 구한다.
  is_empty(list) ::= 리스트가 비었는지를 검사한다.
  is_full(list) ::= 리스트가 꽉 찼는지를 검사한다.
  print_list(list) ::= 리스트의 모든 요소를 표시한다.

6.2 배열로 구현된 리스트

public class ArrayListADT<E> {
    private static final int DEFAULT_CAPACITY = 100;
    private E[] data;
    private int size;

    @SuppressWarnings("unchecked")
    public ArrayListADT() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

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

    public boolean isFull() {
        return size == data.length;
    }

    public int getLength() {
        return size;
    }

    public void insert(int pos, E item) {
        if (isFull()) throw new IllegalStateException("리스트가 꽉 찼습니다.");
        if (pos < 0 || pos > size) throw new IndexOutOfBoundsException("유효하지 않은 위치입니다.");

        for (int i = size - 1; i >= pos; i--) {
            data[i + 1] = data[i]; // 한 칸씩 뒤로 밀기
        }
        data[pos] = item;
        size++;
    }

    public void insertFirst(E item) {
        insert(0, item);
    }

    public void insertLast(E item) {
        insert(size, item);
    }

    public E delete(int pos) {
        if (isEmpty()) throw new IllegalStateException("리스트가 비어 있습니다.");
        if (pos < 0 || pos >= size) throw new IndexOutOfBoundsException("유효하지 않은 위치입니다.");

        E removed = data[pos];
        for (int i = pos; i < size - 1; i++) {
            data[i] = data[i + 1]; // 앞으로 당기기
        }
        data[--size] = null; // 마지막 요소 제거
        return removed;
    }

    public void clear() {
        for (int i = 0; i < size; i++) data[i] = null;
        size = 0;
    }

    public E getEntry(int pos) {
        if (pos < 0 || pos >= size) throw new IndexOutOfBoundsException("유효하지 않은 위치입니다.");
        return data[pos];
    }

    public void printList() {
        System.out.print("List = [ ");
        for (int i = 0; i < size; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println("]");
    }
}

연산	시간 복잡도 (Best / Avg / Worst)	설명
insert(pos, item)	O(1) / O(n) / O(n)	맨 끝 삽입은 빠름, 앞/중간 삽입은 뒤로 밀어야 함
insertFirst(item)	O(n) / O(n) / O(n)	항상 전부 뒤로 밀기
insertLast(item)	O(1) / O(1) / O(1)	size 위치에 삽입
delete(pos)	O(1) / O(n) / O(n)	마지막 삭제는 빠름, 앞쪽 삭제는 전체 당김
clear()	O(n) / O(n) / O(n)	모든 요소 null 처리 반복
getEntry(pos)	O(1) / O(1) / O(1)	배열 인덱싱
getLength()	O(1)	단순 필드 접근
isEmpty()	O(1)	size == 0 검사
isFull()	O(1)	size == capacity 검사
printList()	O(n)	전체 순회 출력

ArrayList로 구현된 리스트

import java.util.*;

public class ArrayListList<E> implements MyList<E> {
    private final List<E> list = new ArrayList<>();

    public void insert(int pos, E item) {
        list.add(pos, item);
    }

    public void insertFirst(E item) {
        list.add(0, item);
    }

    public void insertLast(E item) {
        list.add(item);
    }

    public E delete(int pos) {
        return list.remove(pos);
    }

    public void clear() {
        list.clear();
    }

    public E getEntry(int pos) {
        return list.get(pos);
    }

    public int getLength() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public boolean isFull() {
        return false; // ArrayList는 자동 확장
    }

    public void printList() {
        System.out.println(list);
    }
}

연산	시간 복잡도 (Best / Avg / Worst)	설명
insert(pos)	O(1) / O(n) / O(n)	끝에 삽입은 빠르나, 앞/중간은 모두 뒤로 밀어야 함
insertFirst()	O(n) / O(n) / O(n)	전체를 뒤로 밀어야 함
insertLast()	O(1) / O(1) / O(1)*	마지막에 바로 삽입 (가끔 resize 발생: amortized O(1))
delete(pos)	O(1) / O(n) / O(n)	뒤 요소들을 모두 당겨야 함
deleteLast()	O(1) / O(1) / O(1)	size 감소만으로 충분
get(pos)	O(1) / O(1) / O(1)	배열 인덱싱
clear()	O(1) / O(n) / O(n)	내부 요소 null 처리 반복
isEmpty()	O(1) / O(1) / O(1)	size == 0 비교
isFull()	O(1) / O(1) / O(1)	자동 확장으로 false 고정
printList()	O(n) / O(n) / O(n)	전체 순회 출력

LinkedList 기반 구현

import java.util.*;

public class LinkedListList<E> implements MyList<E> {
    private final LinkedList<E> list = new LinkedList<>();

    public void insert(int pos, E item) {
        list.add(pos, item);
    }

    public void insertFirst(E item) {
        list.addFirst(item);
    }

    public void insertLast(E item) {
        list.addLast(item);
    }

    public E delete(int pos) {
        return list.remove(pos);
    }

    public void clear() {
        list.clear();
    }

    public E getEntry(int pos) {
        return list.get(pos);
    }

    public int getLength() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public boolean isFull() {
        return false;
    }

    public void printList() {
        System.out.println(list);
    }
}

연산	시간 복잡도 (Best / Avg / Worst)	설명
insert(pos)	O(1) / O(n) / O(n)	앞이면 빠르지만, 중간 이상은 순차 탐색 필요
insertFirst()	O(1) / O(1) / O(1)	head 앞에 노드 추가
insertLast()	O(1) / O(1) / O(1)	tail 뒤에 노드 추가
delete(pos)	O(1) / O(n) / O(n)	노드 탐색 후 제거
deleteFirst()	O(1) / O(1) / O(1)	head 연결만 바꿈
deleteLast()	O(1) / O(1) / O(1)	이중 연결 리스트라서 O(1)
get(pos)	O(1) / O(n) / O(n)	head 또는 tail에서 순차 접근
clear()	O(1) / O(n) / O(n)	연결 끊기면 GC가 회수
isEmpty()	O(1) / O(1) / O(1)	size == 0
isFull()	O(1) / O(1) / O(1)	항상 false
printList()	O(n) / O(n) / O(n)	노드 순회 출력

비교

항목	Array (E[])	ArrayList	LinkedList
내부 구조	고정 크기 배열	동적 배열	이중 연결 리스트
크기 조절	❌ 수동 (직접 새 배열 생성)	✅ 자동 확장 (ensureCapacity)	✅ 노드 추가로 자동 확장
인덱스 접근	✅ O(1)	✅ O(1)	❌ O(n) (head부터 탐색)
앞 삽입/삭제	❌ O(n)	❌ O(n)	✅ O(1)
중간 삽입/삭제	❌ O(n)	❌ O(n)	❌ O(n)
뒤 삽입	✅ O(1)*	✅ O(1) (암시적)	✅ O(1)
뒤 삭제	✅ O(1)	✅ O(1)	✅ O(1)
메모리 효율	✅ 가장 우수	✅ 비교적 효율적	❌ 노드마다 포인터 추가 필요
사용 편의성	❌ 낮음	✅ 높음 (List 인터페이스 구현)	✅ 높음 (List + Deque 구현)
표준 인터페이스 지원	❌	✅ (List, Collection)	✅ (List, Deque, Queue)
null 허용	✅	✅	✅
쓰레드 안전성	❌	❌	❌
대표 용도	학습용, 성능 테스트	일반 리스트, 인덱스 중심 로직	빈번한 삽입/삭제, 덱 구조 필요 시

이중 연결 리스트(Doubly linked list) 구현

public class DoublyLinkedList<E> {
    // 내부 노드 클래스
    private static class Node<E> {
        E data;
        Node<E> prev;
        Node<E> next;

        Node(E data) {
            this.data = data;
        }
    }

    private Node<E> head;  // 첫 노드
    private Node<E> tail;  // 마지막 노드
    private int size = 0;

    // 맨 앞에 삽입
    public void addFirst(E data) {
        Node<E> node = new Node<>(data);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
    }

    // 맨 뒤에 삽입
    public void addLast(E data) {
        Node<E> node = new Node<>(data);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
    }

    // 위치에 삽입
    public void insert(int index, E data) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        if (index == 0) {
            addFirst(data);
        } else if (index == size) {
            addLast(data);
        } else {
            Node<E> current = getNode(index);
            Node<E> node = new Node<>(data);
            Node<E> prev = current.prev;
            prev.next = node;
            node.prev = prev;
            node.next = current;
            current.prev = node;
            size++;
        }
    }

    // 노드 삭제 (index 위치)
    public E remove(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        Node<E> toRemove = getNode(index);
        if (toRemove == head) {
            head = head.next;
            if (head != null) head.prev = null;
        } else if (toRemove == tail) {
            tail = tail.prev;
            if (tail != null) tail.next = null;
        } else {
            toRemove.prev.next = toRemove.next;
            toRemove.next.prev = toRemove.prev;
        }
        size--;
        return toRemove.data;
    }

    // 값 조회
    public E get(int index) {
        return getNode(index).data;
    }

    // 내부 노드 조회
    private Node<E> getNode(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        Node<E> current;
        if (index < size / 2) {
            current = head;
            for (int i = 0; i < index; i++) current = current.next;
        } else {
            current = tail;
            for (int i = size - 1; i > index; i--) current = current.prev;
        }
        return current;
    }

    // 전체 출력
    public void print() {
        Node<E> curr = head;
        System.out.print("[ ");
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println("]");
    }

    // 사이즈 반환
    public int size() {
        return size;
    }

    // 비어있는지
    public boolean isEmpty() {
        return size == 0;
    }
}

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

        list.addFirst("B");         // B
        list.addLast("C");          // B C
        list.insert(0, "A");        // A B C
        list.insert(3, "D");        // A B C D
        list.print();               // [ A B C D ]

        list.remove(2);             // remove "C"
        list.print();               // [ A B D ]

        System.out.println("2번째: " + list.get(1));  // B
        System.out.println("크기: " + list.size());   // 3
    }
}

LinkedList 컬렉션이 이중 연결 리스트로 구현되어있다.