[자료구조] 선형 자료 구조

이 포스팅은 주홍철 저 '면접을 위한 CS 전공지식 노트' 5.2장을 토대로 작성되었습니다.
책과는 다르게 Java 코드를 예시로 합니다.

 

선형 자료 구조

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

---

연결 리스트(Linked List)

• 데이터를 노드 단위로 저장
• 각 노드가 포인터를 통해 다음 노드를 가리키며 연결된 구조

 

배열처럼 연속된 메모리 공간에 데이터를 저장하는 것이 아니라,

데이터가 메모리 상에 흩어져 있어도 포인터를 이용하여 순서대로 연결합니다.

 

노드가 동적으로 할당될 수 있으므로 리스트의 크기가 실행 중에 유연하게 변할 수 있습니다.

 

• 삽입/삭제 시간 복잡도: O(1)
  • 포인터 연결만 하면 되므로 빠릅니다.
• 탐색 시간 복잡도: O(n)
  • 원하는 데이터가 나올 때까지 헤드(첫 번째 노드)부터 순차적으로 탐색하므로 느립니다.

 

포인터 연결만 잘하면 단순한 단일 연결 리스트 외에 다양한 형태로 구현할 수 있습니다.

 

자바 컬렉션 프레임워크에서 `java.util.LinkedList` 클래스를 제공하여 편리하게 쓸 수 있습니다.

기본적으로 이중 연결 리스트를 기반으로 구현되어 있습니다.

 

주요 메소드

메소드	설명	복잡도
`add(E element)`	리스트의 맨 끝에 요소를 추가	O(1)
`add(int index, E elment)`	지정된 index 위치에 요소를 삽입	O(1)
`get(int index)`	지정된 index 위치의 요소를 반환	O(n)
`getFirst()`	리스트의 첫 번째 요소를 반환	O(1)
`getLast()`	리스트의 마지막 요소를 반환	이중 연결 리스트인 경우 O(1) 단일 연결 리스트인 경우 O(n)
`indexOf(Object o)`	해당 요소가 처음 나타나는 인덱스 반환	O(n)
`remove(int index)`	지정된 index 위치의 요소를 제거	O(n)

 

LinkedList<String> list = new LinkedList<>();

// 맨 앞 삽입/삭제는 O(1)
list.addFirst("A");     // O(1)
list.removeFirst();     // O(1)

// 맨 끝 삽입/삭제는 O(1)
list.addLast("Z");      // O(1)
list.removeLast();      // O(1)

---

배열(Array)

• 동일한 자료형의 데이터를 연속된 메모리 공간에 순차적으로 저장하는 구조
• 모든 데이터가 메모리에 연속적인 위치에 할당
• 배열이 선언될 때 지정된 크기로 고정되며, 실행 중 크기를 변경할 수 없습니다.
• 인덱스를 기반으로 접근하며, 0부터 시작합니다.

배열은 인덱스를 통해 빠른 접근이 가능하지만, 데이터 삽입/삭제에는 비효율적입니다.

• 탐색/접근 시간 복잡도: O(1)
  • 인덱스를 통해 메모리 주소를 바로 계산하여 원하는 요소에 즉시 접근 가능
  • = 랜덤 접근(random access)
• 삽입/삭제 시간 복잡도: O(n)
  • 중간에 요소를 삽입/삭제하면 그 뒤에 있는 모든 요소들을 한 칸씩 밀거나 당기는 이동 작업 필요

 

배열과 연결 리스트의 핵심 차이

구분	배열 (Array)	연결 리스트 (Linked List)
메모리 배치	물리적으로 연속적	논리적으로 연속적 (물리적으로는 분산)
주요 장점	빠른 접근 (O(1))	빠른 삽입/삭제 (O(1))
주요 단점	느린 삽입/삭제 (O(n))	느린 접근 (O(n))

 

고정 크기라는 특징으로 정적 배열(Static Array)이라고도 합니다.

 

그러나 Java를 포함한 많은 프로그래밍 언어에서 가변 크기 리스트 인터페이스(`java.util.ArrayList`)를 제공합니다.

배열의 크기가 부족해지면 자동으로 더 큰 배열을 새로 할당하고, 데이터를 복사합니다.

이러한 구조를 동적 배열(Dynamic Array)라고 부릅니다.

import java.util.ArrayList;

public class ArrayExample {
    public static void main(String[] args) {
    	// 정적 배열 예시
    
        // 1. 선언 시 크기(5)를 지정
        int[] numbers = new int[5]; 

        // 2. 요소 삽입 (O(1) 접근)
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;

        // 3. 요소 접근 및 탐색 (O(1) 접근)
        System.out.println("세 번째 요소 (인덱스 2): " + numbers[2]); // 30

        // 4. 크기 변경 시도 (불가능!)
        // numbers[5] = 60; // 🛑 오류 발생: Index 5 out of bounds for length 5

        // 5. 순회
        System.out.print("배열 요소: ");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
        System.out.println();
        
        // --------------------------------------------------------------------
        
         // 1. 선언 (초기 크기를 지정할 필요 없음)
        ArrayList<String> fruits = new ArrayList<>();

        // 2. 요소 삽입 (크기가 자동으로 증가)
        fruits.add("Apple");    // O(1) (상각 O(n) 발생 가능)
        fruits.add("Banana");
        fruits.add("Cherry");
        
        // 3. 새로운 요소 추가 (크기가 부족하면 자동으로 내부 배열 확장 및 복사)
        fruits.add("Grape"); // O(1) 또는 O(n) (배열 복사 발생 시)
        
        // 4. 순회
        System.out.print("ArrayList 요소: ");
        for (String fruit : fruits) {
            System.out.print(fruit + " ");
        }
        System.out.println();
    }
}

---

벡터(Vector)

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모를 때 사용
• 인덱스를 통한 빠른 접근 가능
• Java에서는 ArrayList를 주로 사용해 현재는 벡터를 거의 사용하지 않음

 

• 탐색 시간 복잡도: O(1)
  • 인덱스 기반으로 빠르게 찾을 수 있습니다.
• 맨 뒤의 요소를 삭제하거나 삽입하는 시간 복잡도: O(1)
  • 벡터의 크기가 증가되는 시간이 O(1)이기 때문입니다.
• 맨 뒤가 아닌 요소를 삭제하거나 삽입하는 시간 복잡도: O(n)
  • 배열과 같습니다. 

 

현재 자바에서는 Vector 대신 ArrayList를 주로 사용합니다.

기능과 메소드 구성이 거의 동일하나 멀티스레드 환경에서의 동작 방식에 차이가 있습니다.

 

 

Vector는 모든 public 메소드에 `synchronized` 키워드가 붙어 있어

멀티스레드 환경에서 두 개 이상의 스레드가 동시에 이 코드에 접근할 수 없도록 잠금(lock)이 걸려 있습니다.

따라서 Vector 클래스는 멀티스레드 환경에서 안전하게 사용할 수 있는 컬렉션입니다. (Thread-safe)

 

반면 ArrayList는 동기화 처리가 되어 있지 않아 안전하지 않습니다. (Thread-unsafe)

 

그렇다고 Vector가 ArrayList보다 반드시 좋다고 할 수 없습니다.

Vector의 메소드는 스레드-세이프하지만, Vector 인스턴스 객체 자체에는 동기화가 되어 있지 않아 동기화가 완벽하지도 않고,

강제 동기화 때문에 성능이 저하되어서 현대에는 ArrayList를 사용합니다.

---

스택(Stack)

• 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 후입선출: LIFO(Last In First Out) 구조

주요 메소드

스택에서 데이터가 삭제가 이루어지는 유일한 부분을 Top이라고 합니다. 이 Top을 통해 연산을 처리합니다.

Top 한 곳에서만 연산이 이루어지고, 데이터 이동이나 탐색이 필요없어 O(1)로 매우 빠릅니다.

메소드	설명	시간 복잡도
`push()`	스택의 Top에 새로운 데이터를 추가합니다.	O(1)
`pop()`	스택의 Top에 있는 가장 마지막 데이터를 제거하고 그 값을 반환합니다.	O(1)
`peek()`	스택의 Top에 있는 데이터를 제거하지 않고 단순히 확인만 합니다.	O(1)
`empty()`	스택이 비어있는지 (데이터가 없는지) 확인합니다.	O(1)

 

자바의 스택 클래스는 벡터 클래스를 상속 받아 `java.util.Stack`으로 따로 존재하는데

벡터 클래스의 단점 때문에 잘 사용하지 않습니다.

 

따라서 Stack 클래스 대신 Deque 클래스를 사용할 것을 권장하고 있습니다.

Deque(덱)은 양쪽 끝을 모두 사용할 수 있는 큐인데, 큐에 대해서는 다음 문단에서 다루고 있습니다.

간단히 말하자면, 양쪽 끝을 모두 사용할 수 있는 큐로 덱의 한 쪽 끝을 스택의 Top으로 지정하여 사용하면 됩니다.

 

자바의 Deque에서는 덱의 맨 앞쪽을 스택의 Top으로 사용하여 동작합니다.

/* Stack 처럼 사용하기 */
Deque<String> stack = new ArrayDeque<>();

stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
stack.push("e");

System.out.println(stack); // [a, b, c, d, e]

System.out.println(stack.pop()); // e
System.out.println(stack.pop()); // d

System.out.println(stack); // [a, b, c]

---

큐(Queue)

• 먼저 삽입한 데이터가 먼저 나오는 선입선출: FIFO(First In First Out) 구조
• 데이터의 삽입은 한쪽 끝(Rear 또는 Tail)에서 이루어지고, 삭제는 다른 쪽 끝(Front 또는 Head)에서 이루어집니다.

주요 메소드

메소드	역할	설명	시간 복잡도
`offer()` 또는 `add()`	삽입 (Enqueue)	큐의 맨 뒤(Rear)에 데이터를 추가합니다.	O(1)
`poll()` 또는 `remove()`	삭제 (Dequeue)	큐의 맨 앞(Front)에 있는 데이터를 제거하고 그 값을 반환합니다.	O(1)
`peek()` 또는 `element()`	확인 (Check)	큐의 맨 앞(Front) 데이터를 제거하지 않고 확인만 합니다.	O(1)

 

자바에서는 `LinkedList` 인터페이스가 Queue 인터페이스도 함께 구현하고 있어 편리하게 사용할 수 있습니다.

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

public class QueueExample {
    public static void main(String[] args) {
        // Queue 인터페이스를 LinkedList로 구현하여 사용
        Queue<String> queue = new LinkedList<>(); 

        // 1. offer: 데이터 삽입 (FIFO: First-In)
        queue.offer("고객 A"); // 1등으로 들어옴 (Front)
        queue.offer("고객 B");
        queue.offer("고객 C"); // 3등으로 들어옴 (Rear)

        System.out.println("현재 큐 (대기열): " + queue); // [고객 A, 고객 B, 고객 C]

        // 2. peek: Front 요소 확인
        System.out.println("대기열 1순위 (peek): " + queue.peek()); // 고객 A

        // 3. poll: Front 요소 삭제 및 반환 (FIFO: First-Out)
        String servicedClient = queue.poll(); 
        System.out.println("서비스 완료 (poll): " + servicedClient); // 고객 A 제거

        // 4. poll 이후 큐 상태
        System.out.println("poll 후 큐: " + queue); // [고객 B, 고객 C]

        // 5. 다음 순위 확인
        System.out.println("다음 순위: " + queue.peek()); // 고객 B
    }
}

---

참고자료

[자료구조 with C언어] 연결리스트 (Linked List)

연결 리스트 위키백과

🧱 자바 Vector 구조 & 사용법 정리

🧱 ArrayList vs Vector 동기화 & 성능 차이 비교
🧱 자바 Stack 구조 & 사용법 정리