자료구조(Data Structure)

📌 자료구조(Data Structure)란?

• 자료구조는 다수의 자료를 담기 위한 구조이다.
• 데이터의 수가 많아질수록 효율적인 자료구조가 필요하다.

👀 자료구조의 필요성

• 데이터를 효과적으로 저장하고 처리하는 방법에 대해 이해해야 한다.
• 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 계산을 낭비할 여지가 있다.

👀 자료구조의 종류

1. 선형 구조

하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이다.
데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.

• 배열(array)
• 연결리스트(linked list)
• 스택(stack)
• 큐(queue)

2. 비선형 구조

하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조이다.
데이터가 일직선상으로 연결되어 있지 않아도 된다.

• 트리(tree)
• 그래프(graph)

📌 배열과 리스트

배열(array)

• 가장 기본적인 자료구조이다.
• 여러 개의 변수를 담는 공간이다.
• 인덱스가 존재하며 인덱스는 0부터 시작한다.
• 컴퓨터 메모리 공간에서 연속적으로 할당된다.
• 특정한 인덱스에 직접적으로 접근 가능하다 -> 시간복잡도 O(1)

연결리스트(linked list)

• 각 노드가 한 줄로 연결되어 있는 자료구조이다.
• 각 노드는 (데이터, 포인터) 형태를 가진다.
• 컴퓨터의 메모리상에서 주소가 연속적이지 않다.
• 리스트의 크기는 동적으로 변경 가능하다.
• 포인터는 다음 노드의 메모리 주소를 가르킨다. 이를 이용해 삽입과 삭제가 간편하다.(연결성)
• 특정 번째의 원소를 검색 시, 인덱스가 없으므로 순차적으로 원소를 찾아야 하기 때문에 검색 속도가 느리다. -> 시간복잡도 O(N)