[CS] 선형 자료 구조

선형 자료 구조: 요소가 일렬로 나열되어 있는 자료 구조

자료구조	특징	시간 복잡도 (접근/탐색/삽입/삭제)
배열	정적, 고정 크기, 빠른 접근	O(1)/O(n)/O(n)/O(n)
벡터	동적 배열, 랜덤 접근 가능	O(1)/O(n)/O(1n)/O(1n)
연결 리스트	포인터 연결, 삽입/삭제 효율적	O(n)/O(n)/O(1)/O(1)
스택	LIFO (후입선출)	O(n)/O(n)/O(1)/O(1)
큐	FIFO (선입선출)	O(n)/O(n)/O(1)/O(1)

---

연결 리스트 (Linked List)

• 특징: 노드 연결, 공간 효율적
• 종류:
  - 싱글: next만 존재
  - 이중: prev, next 모두 존재
  - 원형 이중: 마지막 노드가 헤드 가리킴

• 삽입/삭제: O(1)
• 탐색: O(n)

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<>();

        l.addFirst(1); // push_front
        l.addLast(2);  // push_back
        l.add(1, 100); // 중간 삽입 (index = 1)

        for (int num : l) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

---

배열 (Array)

• 특징: 고정된 크기, 연속된 메모리 공간
• 장점: 빠른 접근 (O(1))
• 단점: 삽입/삭제 시 전체 이동 → 느림

public class Main {
    public static void main(String[] args) {
        int[] a = new int[10];

        for (int i = 0; i < 10; i++) {
            a[i] = i;
        }

        for (int num : a) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

---

벡터 (Vector, 동적 배열)

• 특징: 크기 자동 증가, 랜덤 접근 가능
• push_back(): 평균 O(1) (amortized)
• 단점: 중간 삽입/삭제 시 느림

import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> v = new ArrayList<>();

        for (int i = 1; i <= 10; i++) {
            v.add(i);
        }

        System.out.println(v); // 전체 출력

        v.remove(v.size() - 1); // pop_back
        System.out.println(v);

        v.remove(0); // erase 첫 번째
        System.out.println(v);

        if (!v.contains(100)) {
            System.out.println("not found");
        }

        Collections.fill(v, 10); // 모든 값을 10으로 채움
        System.out.println(v);

        v.clear(); // 전체 삭제
        System.out.println(v);
    }
}

---

스택 (Stack)

• 특징: LIFO (마지막에 넣은 것 먼저 나옴)
• 사용처: 함수 콜스택, 되돌리기, DFS 등
• 주요 연산:
  - push(), pop(), top()
  

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stk = new Stack<>();

        for (int i = 0; i < 10; i++) {
            stk.push(i);
        }

        while (!stk.isEmpty()) {
            System.out.print(stk.peek() + " ");
            stk.pop();
        }
        System.out.println();
    }
}

---

큐 (Queue)

• 특징: FIFO (먼저 넣은 게 먼저 나옴)
• 사용처: 작업 대기열, BFS 탐색 등
• 주요 연산:
  - push(), pop(), front()
  

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        q.add(1); // enqueue
        System.out.println(q.peek()); // front
        q.poll(); // dequeue
        System.out.println(q.size());
    }
}

---

배열 vs 연결리스트

항목	배열	연결 리스트
접근 속도	O(1)	O(n)
삽입/삭제	느림 (O(n))	빠름 (O(1))
메모리 구조	연속된 공간	비연속, 포인터 연결
활용	참조 많은 작업	삽입/삭제 많은 작업

---

참고: 북스터디 - 면접을 위한 CS 전공지식 노트 (Chapter 5-2)