자료구조) List (리스트)

데이터 표현방식

1. 순차 자료구조
   • 선형 리스트 (Linear/Ordered List)
2. 연결 자료구조
   • 단순 연결리스트 (Linear/Singly Linked List)
   • 원형 연결리스트 (Circular Linked List)
   • 이중 연결리스트 (Doubly Linked List)
   • 이중 원형 연결리스트 (Doubly Circular Linked List)
     => 그리고 이 자료구조들을 활용한 표현 (다행식, 행렬 등...)

---

Linked List (연결 리스트)

랜덤접근이 가능한 배열과 다른, 순차적 자료구조.
저장할 값과 다음 노트를 가리키는 포인터로 이뤄진 '노드'로 구성.

Linked List

Doubly Linked List

Circular Linked List

배열 vs 리스트

배열	리스트
index로 무작위 접근 가능	무작위 접근 불가, 순차적 접근
리스트보다 메모리 적지만, 데이터 삽입/삭제가 비효율적 (순서를 유지하며 자료를 삽입/삭제시, 최악의 경우 모든 데이터를 옮겨야 한다)	배열보다 메모리 크지만, 데이터 삽입/삭제가 효율적

---

입력	출력
첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000) 두 번째 줄부터 N개의 줄에 걸쳐 아래 중 하나의 명령어가 입력됩니다. push x: x를 리스트의 끝에 추가합니다. get x: 리스트의 x번째 원소를 출력합니다. size: 리스트의 크기를 출력합니다. count x: 리스트에 있는 x의 개수를 출력합니다. clear: 리스트를 비웁니다.	각 명령어에 따라 출력값을 한 줄에 나타냅니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String command = scanner.next();

            // push, get, size, count, clear
            if (command.charAt(0) == 'p') {
                int value = scanner.nextInt();
                list.add(value);
            }
            else if (command.charAt(0) == 'g') {
                int idx = scanner.nextInt();
                System.out.println(list.get(idx));
            }
            else if (command.charAt(0) == 's') {
                System.out.println(list.size());
            }
            else if (command.charAt(1) == 'o') {
                int target = scanner.nextInt(), count = 0;
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j) == target) {
                        count++;
                    }
                }
                System.out.println(count);
            }
            else {
                list.clear();
            }
        }
    }
}