[자료구조] LIST 원리

1. List 종류

 

• List는 ‘순서가 있고, 중복을 허용하는’ 컬렉션 인터페이스
• 대표 구현체
  • ArrayList (동적 배열 기반)
  • LinkedList (이중 연결 리스트 기반)

 

 

2. Array(=ArrayList)와 LinkedList의 차이점

 

▶ ArrayList 원리

• 데이터가 메모리 상에 연속적으로 나열됨.
• Index(주소)를 통해 데이터에 즉시 접근 가능 (Random Access).
• 공간이 꽉 차면 더 큰 새 배열을 만들고(=복사) 데이터를 전부 이사(Copy)시켜야 함.
• 중간에 데이터를 삭제하면, 뒤에 있는 데이터들을 한 칸씩 앞으로 당겨야 함(Shift).

public class MyArrayList {
    private Object[] elements; // 내부는 실제 배열(Array)로 되어 있음
    private int size = 0;

    // 1. 조회 (Get)
    // 원리: 배열 인덱스로 바로 접근함. 속도 매우 빠름 O(1).
    public Object get(int index) {
        return elements[index]; 
    }

    // 2. 추가 (Add)
    // 원리: 공간이 남으면 그냥 넣음. 
    // 꽉 차면 2배 크기 배열을 만들고 이사(Copy) 시킴. 속도 느려질 수 있음.
    public void add(Object value) {
        if (size == elements.length) {
            growArray(); // 배열 크기 늘리기 (비용이 큼)
        }
        elements[size] = value;
        size++;
    }

    // 3. 삭제 (Remove)
    // 원리: 중간 데이터를 빼면 구멍이 생기므로, 뒤의 요소들을 전부 앞으로 당겨야 함. O(n)
    public void remove(int index) {
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1]; // 한 칸씩 앞으로 당김 (Shift)
        }
        size--;
    }
}

• 내부에 Object[] 배열을 들고 있음.
• add(e) 하면 배열이 꽉 찼는지 확인함.
• 꽉 찼으면 더 큰 배열을 새로 만들고 기존 요소를 복사함(리사이즈).
• get(i)는 배열 인덱싱으로 바로 접근함.

 

 

▶ LinkedList 원리

ㄴ  보물찾기 쪽지 첫 번째 쪽지를 찾으면 "두 번째 쪽지는 나무 아래에 있어"라고 적혀있어! 라고 말하는 것 

• 데이터가 메모리 상에 흩어져 저장될 수 있음.
• 각 데이터(Node)가 다음 데이터의 **주소(Reference)**를 들고 있음.
• 특정 순서(예: 5번째)를 찾으려면 첫 번째부터 타고 들어가야 함 (Sequential Access).
• 중간 삽입/삭제 시, 데이터를 옮길 필요 없이 **주소 연결(Link)**만 바꿔주면 됨.

// 데이터를 담는 그릇 (Node)
class Node {
    Object data;
    Node next; // 다음 노드의 주소를 가리킴 (핵심)
}

public class MyLinkedList {
    private Node head; // 첫 번째 노드만 알고 있음

    // 1. 조회 (Get)
    // 원리: 인덱스 개념이 없음. ✨ head부터 next를 타고 원하는 횟수만큼 이동해야 함. O(n)
    public Object get(int index) {
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next; // 보물찾기처럼 다음 위치로 이동
        }
        return current.data;
    }

    // 2. 중간 삽입/삭제
    // 원리: 앞뒤 노드의 주소(next)만 바꿔주면 됨. 데이터 이동(Shift) 없음. O(1) (단, 위치 탐색 시간 제외)
    public void insertAfter(Node prevNode, Object value) {
        Node newNode = new Node();
        newNode.data = value;
        
        newNode.next = prevNode.next; // 새 노드가 기존의 다음 노드를 가리킴
        prevNode.next = newNode;      // 앞 노드가 새 노드를 가리킴
        // 끝. 배열처럼 뒤의 데이터를 밀어낼 필요 없음.
    }
}

• 노드 기반임.
• 인덱스 접근 느림(O(n)) 됨.
• 삽입/삭제는 링크 변경으로 처리됨(단, 위치 탐색 비용은 별개임).

 

 

3. 자료구조 사용 예시

 

ㄴ 기본은 ArrayList를 우선 선택하고, “정말 LinkedList가 유리한 상황인지”를 따져보는 게 안전

 

▶  ArrayList가 좋은 경우

• 조회가 많음 (get(i), 반복 접근, 인덱스 기반 처리)
• 끝에 추가가 많음 (add(e)가 대체로 빠름: 리사이즈가 가끔 발생하더라도 평균적으로 효율적)
• 메모리 효율이 중요함(연속 배열이라 오버헤드가 상대적으로 적음)

▶  LinkedList가 좋은 경우

• “앞/뒤”에서 삽입/삭제가 매우 빈번함 (큐/덱처럼)
• 이미 ListIterator 같은 걸로 “현재 노드 위치”를 잡고 그 주변에 삽입/삭제를 계속할 때
  • 단순히 add(0, x)를 많이 한다고 무조건 유리한 게 아님(매번 위치 찾으면 결국 느릴 수 있음)

❌ 이건 해당 안 됨
list.add(500_000, x);
list.remove(500_000);
list.add(500_000, y);

• 매번 index로 접근함
• 내부적으로 처음/끝부터 500,000번째까지 탐색함
• LinkedList라도 매번 O(n) 발생함
• 👉 이 경우 ArrayList보다 나을 게 없음

✅ 좋은 예: 위치를 한 번 잡고 반복 변경
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) list.add(i);

// 🔥 한 번만 위치를 찾음
ListIterator<Integer> it = list.listIterator(500_000);

// 🔥 그 위치를 기준으로 반복 수정
for (int i = 0; i < 1000; i++) {
    it.add(-1);   // 현재 위치에 삽입 (탐색 없음)
    it.previous();
    it.remove();  // 바로 앞 노드 제거 (탐색 없음)
}

 

 

▶  원리(중요 포인트)

• ArrayList 중간 삽입/삭제: shift 발생함.
• LinkedList 중간 삽입/삭제: 링크만 변경함.
• LinkedList는 “찾는 비용”이 먼저 듦.
  • 그래서 “중간 삽입/삭제가 많다 = 무조건 LinkedList”가 아님.
  • “중간 위치를 이미 잡고 반복적으로 바꾸는가”가 핵심임.

상황	추천 자료구조	이유 (원리 기반)
데이터 조회가 많을 때	ArrayList	인덱스($O(1)$)로 바로 접근하므로 속도가 매우 빠름.
데이터 끝에만 추가할 때	ArrayList	배열 크기만 충분하다면 맨 뒤에 넣는 것은 빠름.
데이터 중간 삽입/삭제가 잦을 때	LinkedList	데이터를 밀거나 당기는(Shift) 비용 없이, 주소 연결만 바꾸면 되므로 효율적임.
데이터 개수를 예측할 수 없을 때	LinkedList	ArrayList는 크기를 늘릴 때마다 복사 비용(Copy)이 발생하지만, LinkedList는 노드만 추가하면 됨.

 

 

4.다른 자료구조와의 차이점

 

(1) List (순서가 있는 저장소)

• 특징: 줄을 서는 것과 같음. 들어온 **순서(Order)**가 중요하고 유지됨.
• 중복: 똑같은 데이터가 여러 번 들어갈 수 있음.
• 접근: "3번째 사람 나와" (인덱스 사용).

(2) Map (키-값 쌍 저장소)

 

ㄴ 사물함 사물함 번호(Key)를 알면 바로 물건(Value)을 꺼낼 수 있음. 사물함 번호는 겹칠 수 없음

 

• 특징: 순서보다 **검색(Lookup)**이 중요함. Key와 Value가 짝을 이룸.
• 중복: Key는 중복 불가능(유일해야 함), Value는 중복 가능.
• 원리: 내부적으로 Hash Function을 사용해 Key가 저장될 위치를 즉시 계산함. 그래서 데이터가 아무리 많아도 검색 속도가 $O(1)$에 가까움.

(3) Set (집합)

 

ㄴ 초대장 명단 이미 명단에 있는 사람은 또 적지 않음. 순서는 중요하지 않고 "명단에 있는가?"가 중요.

 

• 특징: 순서 없음, 중복 불가능.
• 목적: 데이터의 유일성을 보장하고 싶을 때 사용. (예: 로또 번호 추첨)

 

5. 코드로 보는 차이

 

(A) ArrayList 중간 삽입이 왜 느린가: shift 확인

import java.util.*;

public class Demo {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < 5; i++) a.add(i); // [0,1,2,3,4]

        a.add(2, 99); // index 2에 삽입 -> 2부터 끝까지 한 칸씩 밀림
        System.out.println(a); // [0,1,99,2,3,4]
    }
}

 

(B) LinkedList가 “항상” 중간 삽입이 빠른 게 아닌 이유: 탐색 비용

import java.util.*;

public class Demo2 {
    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<>();
        for (int i = 0; i < 1_000_000; i++) l.add(i);

        // "중간에 넣기" 자체는 링크만 바꾸면 되지만,
        // index 500_000까지 가는 데 이미 시간이 듦.
        l.add(500_000, 123);
    }
}

 

(C) Map이 “키로 빠르게 찾는 느낌”이 나는 이유 (HashMap)

import java.util.*;

public class Demo3 {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("apple", 10);
        m.put("banana", 20);
    }
}