자료구조 배열, 리스트, 링크드 리스트, 스택, 큐

JAVA로 구현하는 알고리즘과 디자인 패턴 공부: 핵심 자료구조 1편

1. 자료구조란 무엇일까요?

개념: 여러 데이터의 묶음을 효율적으로 저장하고 사용하기 위한 구조적인 방법을 의미합니다. 데이터에 맞는 자료구조를 사용하면 코드의 성능을 극대화할 수 있습니다.

---

2. 배열 (Array)

개념: 같은 타입의 데이터 여러 개를 연속된 메모리 공간에 저장하는 가장 기본적인 자료구조입니다. 각 데이터는 **인덱스(index)**를 통해 직접 접근할 수 있습니다.

• 특징 및 시간 복잡도:
  • 조회 (Access): O(1) - 인덱스를 알면 즉시 해당 위치의 데이터에 접근할 수 있어 매우 빠릅니다.
  • 추가/삭제 (Insertion/Deletion): O(n) - 중간에 데이터를 추가하거나 삭제하려면, 그 뒤의 모든 요소들을 한 칸씩 밀거나 당겨야 해서 비효율적입니다.
  • 고정된 크기: 처음 생성할 때 크기가 정해지며, 나중에 변경할 수 없습니다.
• Java 코드 예시:
• Java

   

  // 1. 배열 선언 및 초기화
  int[] numbers = new int[5]; // 크기가 5인 정수 배열 생성
  
  // 2. 데이터 할당
  numbers[0] = 10;
  numbers[1] = 20;
  numbers[2] = 30;
  
  // 3. 데이터 조회 (O(1)의 위력!)
  // 인덱스 2에 바로 접근하여 값을 가져온다.
  System.out.println("인덱스 2의 값: " + numbers[2]); // 출력: 30
  
  // 4. 데이터 변경
  numbers[1] = 99;
  

• 실제 사용 예:
  • 체스판, 바둑판: 2차원 배열을 사용하여 각 칸의 상태를 표현하기에 완벽합니다.
  • 단순 데이터 집합: 크기가 정해져 있고 조회가 빈번한 데이터 묶음을 다룰 때 가장 효율적입니다.

---

3. 리스트 (List)

개념: 배열과 비슷하지만, 크기가 고정되지 않고 동적으로 변할 수 있는 자료구조입니다. Java에서는 주로 ArrayList와 LinkedList 두 가지 구현체를 사용합니다.

가. ArrayList

개념: 내부적으로 배열을 사용하여 구현된 리스트입니다. 배열의 장점(빠른 조회)과 리스트의 장점(크기 조절)을 결합했습니다.

• 특징 및 시간 복잡도:
  • 조회 (Access): O(1) - 내부가 배열이므로 인덱스를 통한 접근이 매우 빠릅니다.
  • 맨 끝에 추가/삭제: 평균 O(1) - 맨 뒤에 데이터를 추가/삭제하는 것은 빠릅니다. (단, 내부 배열의 크기가 꽉 차서 더 큰 배열로 복사해야 하는 경우에는 일시적으로 $O(n)$이 소요될 수 있습니다.)
  • 중간에 추가/삭제: O(n) - 배열과 마찬가지로 중간 데이터 변경 시 뒤 요소들의 이동이 필요해 느립니다.
• Java 코드 예시:
• Java

   

  // 1. ArrayList 생성
  List<String> fruits = new ArrayList<>(); // 크기가 동적으로 변함
  
  // 2. 데이터 추가 (주로 맨 뒤에 추가)
  fruits.add("Apple");
  fruits.add("Banana");
  fruits.add("Cherry");
  
  // 3. 중간에 데이터 추가 (O(n) - 비효율적)
  // "Banana"와 "Cherry"가 한 칸씩 뒤로 밀려난다.
  fruits.add(1, "Orange"); // [Apple, Orange, Banana, Cherry]
  
  // 4. 데이터 조회 (O(1) - 매우 효율적)
  System.out.println("인덱스 2의 과일: " + fruits.get(2)); // 출력: Banana
  

나. LinkedList

개념: 각 데이터 조각(노드, Node)이 다음 노드의 주소를 가리키는 방식으로 연결된 리스트입니다. 데이터들이 메모리상에 흩어져 있습니다.

• 특징 및 시간 복잡도:
  • 조회 (Access): O(n) - 특정 인덱스의 데이터를 찾으려면 첫 번째 노드부터 순서대로 따라가야 해서 느립니다.
  • 추가/삭제: O(1) - 특정 노드를 알고 있다면, 그 노드의 앞/뒤 연결 관계만 바꿔주면 되므로 매우 빠릅니다.
  • 데이터의 잦은 추가/삭제가 일어나는 경우 ArrayList보다 훨씬 유리합니다.
• Java 코드 예시:
• Java

   

  // 1. LinkedList 생성
  List<String> animals = new LinkedList<>();
  
  // 2. 데이터 추가
  animals.add("Lion");
  animals.add("Tiger");
  animals.add("Bear");
  
  // 3. 데이터 추가/삭제 (O(1) - 효율적)
  // 특정 위치를 알고 있다면 연결 정보만 수정하면 되므로 빠르다.
  // (물론 그 위치를 찾는 데는 O(n)이 걸리므로, Iterator를 함께 사용할 때 진정한 효율이 나옴)
  animals.remove(1); // "Tiger" 삭제
  

• Spring Framework에서의 활용:
  • @OneToMany 같은 JPA 연관관계 매핑 시, 컬렉션 타입으로 List 인터페이스를 주로 사용합니다. 이때 조회는 많고 추가/삭제가 적다면 ArrayList를, 엔티티의 추가/삭제가 빈번하다면 LinkedList를 고려해볼 수 있습니다. 하지만 대부분의 경우 JPA가 제공하는 영속성 관리 기능과 조회 성능 때문에 ArrayList가 더 보편적으로 사용됩니다.

---

4. 스택 (Stack) 📚

개념: **"마지막에 들어온 것이 가장 먼저 나간다(Last-In, First-Out, LIFO)"**는 원칙으로 동작하는 자료구조입니다. 마치 접시를 쌓아 올리고, 사용할 땐 맨 위 접시부터 꺼내는 것과 같습니다.

• 주요 연산:
  • Push: 스택의 맨 위에 데이터를 추가합니다.
  • Pop: 스택의 맨 위 데이터를 꺼내고 삭제합니다.
  • Peek: 스택의 맨 위 데이터를 삭제하지 않고 확인만 합니다.
  • 모든 연산의 시간 복잡도는 **O(1)**로 매우 빠릅니다.
• Java 코드 예시:
• Java

   

  Stack<String> browserHistory = new Stack<>();
  
  // 웹 페이지 방문 (Push)
  browserHistory.push("google.com");
  browserHistory.push("naver.com");
  browserHistory.push("github.com");
  
  System.out.println("현재 페이지: " + browserHistory.peek()); // 출력: github.com
  
  // 뒤로 가기 (Pop)
  String previousPage = browserHistory.pop();
  System.out.println("뒤로가기 후 페이지: " + browserHistory.peek()); // 출력: naver.com
  

• 실제 사용 예:
  • 웹 브라우저의 '뒤로 가기': 방문 페이지 주소를 스택에 push하고, '뒤로 가기' 버튼을 누르면 pop하여 이전 페이지로 돌아갑니다.
  • 함수 호출 스택(Call Stack): 프로그램에서 함수가 호출될 때마다 해당 함수의 정보가 스택에 쌓이고, 함수 실행이 끝나면 스택에서 제거됩니다. (재귀 호출 시 에러가 StackOverflowError인 이유!)
  • Spring Security: 인증/인가 처리 과정에서 사용자의 요청 처리 필터들이 체인 형태로 동작하는데, 이는 스택 구조와 유사한 방식으로 관리될 수 있습니다.

---

5. 큐 (Queue) 🎟️

개념: **"먼저 들어온 것이 가장 먼저 나간다(First-In, First-Out, FIFO)"**는 원칙으로 동작합니다. 은행 창구나 맛집 대기 줄을 생각하면 쉽습니다.

• 주요 연산:
  • Enqueue (add/offer): 큐의 맨 뒤에 데이터를 추가합니다.
  • Dequeue (remove/poll): 큐의 맨 앞에서 데이터를 꺼내고 삭제합니다.
  • Peek: 큐의 맨 앞 데이터를 삭제하지 않고 확인만 합니다.
  • 스택과 마찬가지로 모든 연산의 시간 복잡도는 **O(1)**입니다.
• Java 코드 예시:
• Java

   

  // Queue는 인터페이스이므로, 구현체인 LinkedList를 사용한다.
  Queue<String> printerQueue = new LinkedList<>();
  
  // 인쇄 작업 요청 (Enqueue)
  printerQueue.offer("문서1.hwp");
  printerQueue.offer("문서2.pptx");
  printer_queue.offer("문서3.xlsx");
  
  // 인쇄 시작 (Dequeue)
  while (!printerQueue.isEmpty()) {
      String document = printerQueue.poll();
      System.out.println(document + "를 인쇄합니다.");
  }
  // 출력: 문서1.hwp -> 문서2.pptx -> 문서3.xlsx 순서
  

• 실제 사용 예:
  • 프린터 인쇄 대기열: 인쇄 요청이 들어온 순서대로 작업을 처리합니다.
  • 메시지 큐 (MQ): 대용량 트래픽 처리 시, 요청을 바로 처리하지 않고 큐에 잠시 쌓아두고 서버가 처리 가능한 만큼 순차적으로 가져가서 처리하는 방식에 사용됩니다. (예: RabbitMQ, Kafka)
  • Spring Framework: @Async 비동기 메서드 호출이나 메시징 시스템(JMS) 연동 시, 내부적으로 태스크 큐(Task Queue)를 사용하여 작업들을 관리합니다.

---

6. 문제 제시 및 답변

개념을 잘 이해했는지 확인해볼 시간입니다! 🧐

문제: 웹 브라우저의 '뒤로 가기'와 '앞으로 가기' 기능을 구현하려고 합니다. 사용자가 새로운 페이지로 이동하거나 '뒤로/앞으로 가기'를 할 때, 페이지 방문 기록을 효율적으로 관리하려면 어떤 자료구조를 조합해서 사용하는 것이 가장 좋을까요?

답변:

이 기능은 **두 개의 스택(Stack)**을 사용하여 효율적으로 구현할 수 있습니다.

1. backStack (뒤로 가기 스택): 사용자가 방문한 페이지 기록을 저장합니다.
2. forwardStack (앞으로 가기 스택): 사용자가 '뒤로 가기'를 했을 때, 원래 있던 페이지를 저장합니다.

• 동작 방식:
  • 새 페이지 방문: backStack에 현재 페이지를 push하고, forwardStack은 비웁니다.
  • '뒤로 가기' 버튼 클릭: backStack에서 페이지를 pop하여 forwardStack에 push합니다. backStack의 peek이 이제 현재 페이지가 됩니다.
  • '앞으로 가기' 버튼 클릭: forwardStack에서 페이지를 pop하여 backStack에 push합니다. backStack의 peek이 현재 페이지가 됩니다.

이 방식을 사용하면 '뒤로 가기'와 '앞으로 가기' 연산 모두 $O(1)$의 시간 복잡도로 매우 빠르게 처리할 수 있습니다.