5.2 선형 자료 구조

참고한 책: 면접을 위한 CS 전공지식 노트 (http://www.yes24.com/Product/Goods/108887922)

5. 자료구조

    5.2. 선형 자료 구조

        5.2.1. 연결 리스트

        5.2.2. 배열

        5.2.3. 벡터

        5.2.4. 스택

        5.2.5. 큐

 

p. 237

5.2.1 연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대확시킨 자료 구조

삽입과 삭제 O(1)

탐색 O(n)

 

자바에서의 이중 연결 리스트

>> https://st-lab.tistory.com/169#%EC%A0%84%EC%B2%B4

 

자바에서의 싱글 연결 리스트

>> https://st-lab.tistory.com/167

 

자바에서의 원형 이중 연결 리스트

>> https://inpa.tistory.com/entry/DS-%F0%9F%A7%B1-Circular-Doubly-LinkedList-%EC%A7%81%EC%A0%91-%EA%B5%AC%ED%98%84-%ED%95%B4%EB%B3%B4%EA%B8%B0-JAVA

 

p. 239

5.2.2 배열

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합. 

중복을 허용하고 순서가 있음.

탐색 O(1)

삽입, 삭제 O(n)

데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋음.

배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용

 

랜덤 접근과 순차적 접근

랜덤 접근(직접 접근): 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능. 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대.

 

배열과 연결리스트 비교

	탐색	추가	삭제
배열	빠름	느림	느림
연결리스트	트림	빠름	빠름

 

자바 배열

>> https://m.blog.naver.com/heartflow89/220950491600

 

p. 241

5.2.3 벡터

동적으로 요소를 할당할 수 있는 동적 배열

중복 허용, 순서 있음, 랜덤 접근 가능.

맨 뒤 요소 삭제, 삽입 O(1)

맨뒤나 맨 앞이 아닌 요소 삭제 삽입 O(n)

 

(C++ 기준 {2의 n제곱(n>=0)} + 1 번로 push_back()으로 값을 넣을 때마다 2의 n 제곱만큼 용량을 늘림.

 

자바 벡터

>> https://crazykim2.tistory.com/570

 

p. 244

5.2.4 스택

LIFO(Last In First Out)

삽입 삭제 O(1)

탐색 O(n)

재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임.

 

자바 스택 

>> https://go-coding.tistory.com/5

 

p. 245

5.2.5 큐

FIFO(First In First Out)

삽입 삭제 O(1)

탐색 O(n)

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됨.

 

자바 큐

>> https://crazykim2.tistory.com/571