자료구조 정리

설탕유령·2022년 9월 3일

배열, 연결리스트, 스택, 큐, 해시테이블, 그래프, BFS, DFS

배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

[배열]

자료 구조는 크게 메모리 공간 기반의 연속(Contiguous) 방식과 포인터 기반의 연결(Link) 방식으로 나뉨

배열은 이중 연속 방식의 가장 기본이 되는 자료형
연결 방식의 가장 기본이 되는 자료형은 '연결 리스트'
추상 자료형(Abstract Data Type, 이하 ADT)의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 함
예를 들어, 스택은 연결 리스트로 구현, 큐는 배열로 구현
반대의 경우도 가능

배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당 받는 작업을 수행하는 자료형

 # 파이썬에서 배열은 리스트 라고 불림
 # 다음은 리스트 변수에 0부터 4까지 부여하는 코드
 list = [0, 1, 2, 3, 4]

물리 메모리, 즉 실제 메로리에는 배열 요소의 값 0, 1, 2, 3, 4가 순서대로 배치됨
int는 4 바이트를 사용 함으로
선언된 배열에 메모리 주소는 4개를 기준으로 나뉨
list[0] = 0x00, 0x01, 0x02, 0x03
list[1] = 0x04, 0x05, 0x06, 0x07
list[2] = 0x08, 0x09, 0x0A, 0x0B
...
연속적으로 주소에서 할당 되기 때문에 배열은 어느 위치에나 O(1)에 조회가 가능
Ex) 배열에 3번째 주소에 접근하고자 하는 경우 (3-1)x4 = 08
0x08번 주소부터 참조하는 것으로 0(1) 접근 가능

[연결 리스트]

연결 리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.

연결 리스트(Linked List는 컴퓨터 과학에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나

다양한 추상 자료형(ADT) 구현의 기반이 됨
동적으로 새로운 노드를 삽입하거나 삭제하기가 간편
연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 됨으로 관리가 쉬움

# 파이썬에서 구현되는 리크드 리스트 예제
class ListNode:
    def __init__(self, val=0, next=None):
    	# 현재 리스트에 담길 값
        self.val = val
        # 연결 될 다음 리스트의 주소
        self.next = next