[Java] CS - 선형 자료구조

다음의 자료구조는 모두 데이터가 선형으로 연결된 형태를 가지고 있다.

Array

• 연속적인 메모리 영역에 저장되는 동일한 타입 원소들의 집합
• 선언 시에 배열의 사이즈가 고정된다.
  • 기억 장소의 추가가 어려움.
• random access 가 가능하므로 특정 인덱스 데이터에 접근이 빠르다.(O(N))
• 할당된 크기에서 벗어난 삭제 혹은 삽입 연산이 불가능하다.

List

• JAVA에는 Vector, ArrayList, LinkedList, Stack등의 구현체가 존재하며, 주로 ArrayList와 LinkedList를 자주 사용한다.
• 크기가 가변적이다.
• 동일 타입 원소를 연속적으로 저장한다.

ArrayList vs LinkedList

• ArrayList와 LinkedList의 주요 차이점은 다음과 같다.

클래스	데이터 구조	임의 접근	삽입/삭제 성능
ArrayList	배열	빠름	느림
LinkedList	이중 연결 리스트	느림	빠름

• ArrayList
  • 가변 배열 형태로 저장된 구조이다.
  • 내부 배열의 데이터가 가득 차면 기존 배열을 새로운 배열에 복사하는 방식을 사용한다.
    • 배열을 사용하므로 데이터 접근 속도가 빠르다.
  • 데이터의 추가/삭제시 내부 배열 덮어쓰기 방식으로 데이터를 이동시킨다.
    • 중간 데이터 삽입/삭제시 내부 배열 복사가 일어나 비효율적이다.
  • 기능적으로 Vector와 동일하나 성능이 개선되었다.
• LinkedList
  • 노드를 연결한 구조로 구성되어 있다.
    • 각 노드는 데이터와 다음 노드 주소를 저장한다.
    • 각 데이터들은 물리적으로 불연속적으로 존재한다.
    • 자기 자신의 데이터 값과 다음 노드의 주소값을 저장한다.
    • 다음 노드의 주소값만 변경해주면 되므로 중간 데이터의 추가/삭제가 효율적이다.(O(1))
    • 인덱스가 없어서 중간 데이터를 읽기 비효율적이다. (O(n))
• 각 자료구조의 성능 차이는 다음과 같다.

클래스	끝에 추가	중간/처음에 추가	끝에서 삭제	중간/처음에서 삭제
ArrayList	빠름	느림	빠름	느림
LinkedList	느림	빠름	느림	빠름

• Stack, Queue 두 자료구조는 자료를 특정 순서대로 저장 및 핸들링이 가능하게 하는 자료구조이다.
• 이 두가지 자료구조의 주된 차이점은 자료의 추가와 삭제 순서이다.

Queue

• First In First Out : 먼저 들어간 데이터를 먼저 꺼낸다.
• 예시 : 인쇄 작업 대기 목록, 버퍼

Queue<Runnable> tasks = new LinkedList<>();

// Enqueue tasks
tasks.add(() -> System.out.println("Task 1"));
tasks.add(() -> System.out.println("Task 2"));
tasks.add(() -> System.out.println("Task 3"));

// Dequeue and execute tasks
while (!tasks.isEmpty()) {
    Runnable task = tasks.remove();
    task.run();
}

Stack

• Last In First Out : 마지막에 저장한 데이터를 가장 먼저 꺼낸다.
• 예시 : undo / redo 기능

String str = "Hello World";
Stack<Character> stack = new Stack<>();

// Push each character of the string onto the stack
for (char c : str.toCharArray()) {
    stack.push(c);
}

// Pop each character from the stack to create the reversed string
String reversedStr = "";
while (!stack.isEmpty()) {
    reversedStr += stack.pop();
}

System.out.println(reversedStr); // Output: dlroW olleH