자료 구조 - 선형 자료 구조

참고 링크

한 종류의 데이터가 선처럼 길게 나열된 자료 구조

랜덤 접근 가능

모든 자료에 O(1)으로 접근이 보장되는 자료 구조들

배열

해시

해시 함수에 키값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다

언제나 O(1)가 보장되는 것은 아님

(파이선의 해시는 딕셔너리(dictionary)라고 부른다)

랜덤 접근 불가능

모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다.

스택(Stack)

• 먼저 들어간 자료가 나중에 나오는 자료구조 (LIFO)
• 자료를 넣는 push
• 자료를 빼는 pop

큐(Queue)

• 먼저 들어간 자료가 먼저 나오는 구조 (FIFO)
• 자료를 넣는 Enqueue함수와 자료를 빼내는 Dequeue 함수를 가짐
• 연결 리스트로 구현한다 LinkedList

데크(Deque)

• 스택과 큐의 융합형태
• 양쪽 끝에서 삽입과 삭제가 모두 가능하다
• 보통 입력이나 출력 중 하나를 한 쪽 입구만 가능하게 제한하는 형태가 많이 쓰임

링크드 리스트(LinkedList)

• 연결 리스트라고 불림
• 값과 다음 노드를 가지고 있으다
• 옵션으로 이전 노드를 가지게 할 수도 있으며 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다.
• 또한 중간에서 삽입과 삭제를 할 수 있다.
• 가장 간단하게 구현한 것은 큐
• 링크드 리스트는 원소들이 이곳저곳에 흩어져있어 구현체의 속도가 느리기 때문에 잘 사용되지 않는 편