[자료구조] 자료구조 (Data Structure) 개요

이 글은 자료구조의 개념 및 종류에 관한 기록입니다.

자로구조의 개념

자료구조(Data Structure)는 효율적인 접근 및 수정을 가능하도록 하는 자료의 조직, 관리, 저장을 의미합니다. 즉, 자료구조는 대량의 데이터를 효율적으로 관리할 수 있는 데이터 구조를 말합니다.

자료구조의 종류

• 배열 (Array) : 데이터를 나열하고, 각 데이터를 인덱스에 대응하여, 인덱스로 데이터에 접근할 수 있도록 하는 데이터 구조
• 연결 리스트 (Linked list) : 데이터와 포인터로 구성된 노드를 단위로 하는 데이터 구조
  • 이중 연결 리스트 : 데이터와 이전 노드의 포인터와 다음 노드의 포인터로 구성된 노드를 단위로 하는 데이터 구조 (처음 노드의 이전 노드 X, 마지막 노드의 다음 노드 X)
  • 원형 연결 리스트 : 데이터와 다음 노드의 포인터로 구성된 노드를 단위로 하는 데이터 구조 (마지막 노드의 다음 노드가 처음 노드)
• 스택 (Stack) : 가장 나중에 넣은 데이터를 가장 먼저 꺼낼 수 있는 데이터 구조
• 큐 (Queue) : 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 데이터 구조
• 덱 (Deque) : 양쪽에서 데이터를 넣고 빼는 것을 가능하도록 하는 데이터 구조
• 해시 테이블 (Hash Table) : 키에 데이터를 저장하여, 키로 데이터에 접근할 수 있도록 하는 데이터 구조
• 그래프 (Graph) : 노드와 엣지로 구성된 데이터 구조
  • 방향 그래프 : 엣지가 방향성을 갖는 경우
  • 무방향 그래프 : 엣지가 방향성을 갖지 않는 경우
• 트리 (Tree) : 노드와 브랜치로 구성된 데이터 구조
  • 일반 트리
  • 이진 트리 : 자식 노드가 최대 두 개인 경우

자료구조 in Python

• 리스트 (List) : 시퀀스 자료형 (순서 O)
  • 스택, 큐, 덱으로 활용 가능
• 튜플 (Tuple) : 시퀀스 자료형 (순서 O), 값의 생성, 삭제, 수정 허용 X
• 집합 (Set) : 시퀀스 자료형 X (순서 X), 값의 중복 허용 X
• 딕셔너리 (Dictionary) : 매핑형 자료형
  • 해시 테이블 지원
• collections 모듈 : 파이썬의 내장 컨테이너 list, tuple, set, dictionary에 대한 대안으로서 특수 컨테이너를 제공하는 모듈