[Data Structure] 자료구조(Data Structure)란? (선형&비선형 자료구조)

 

🗨 개인적인 공부 목적으로 정리한 내용입니다.

 

 

 

 

 

⭐자료구조는 데이터를 효율적으로 저장하고, 관리하고, 사용할 수 있도록 조직화하는 방법이나 체계를 의미한다.

 

 

 

 

 

자료구조(Data Structure)는 컴퓨터 과학에서 매우 중요한 개념이다. 

자료구조가 다양한 알고리즘의 성능과 효율성을 크게 좌우하기 때문이다. 

따라서, 다양한 프로그램 설계나 문제 해결을 위해서 적합한 자료구조를 선택해야 하므로 각 자료구조에 대해 잘 알아두어야 한다.

 

요리만큼 중요한 요리 재료 관리!

 

---

📌 자료구조란? 

간단하게 표현하자면, 자료구조는 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계를 정하는 것을 말한다.

 

우리가 일상에서 물건들을 정리하는 방법을 떠올려보자.

예를 들어, 여러 개의 칸으로 나누어져 있는 책장에 책을 정리하는 상황을 가정해 보자. 각 칸에는 1개의 책만 들어간다.

책장의 크기는 책 30권이 들어갈 정도의 크기이다. 책장의 크기는 정해져 있으므로 우리는 그 책장에 들어갈 정도의 책만 들고 와야 정리가 가능하다. 

 

자료구조 중 하나인 배열(Array)을 이 책장에 비유할 수 있다.

책장과 배열(Array)

 

책이 데이터이고 책장이 메모리라고 생각하면, 배열의 개념을 컴퓨터의 관점에서 쉽게 이해할 수 있다.

 

이처럼 우리가 일상에서 물건을 정리하여 보관하는 것과 마찬가지로, 컴퓨터도 데이터를 효율적으로 저장, 관리, 검색하기 위해 체계적인 구조를 필요로 한다. 여기서 말하는 체계적인 구조가 바로, 자료구조이다.

 

자료구조는 데이터를 효율적으로 저장하고, 관리하고, 사용할 수 있도록 조직화하는 방법이나 체계를 의미한다.

이는 컴퓨터에서 데이터를 어떻게 저장하고, 어떤 방식으로 접근할지를 결정하는 데 필수적인 역할을 한다.

 

 

 

 

 

📌 자료구조의 목적과 중요성

자료구조의 목적은 무엇이고 왜 중요할까?

 

🔖 1) 효율적인 데이터 관리

자료구조는 데이터를 체계적으로 저장하고 조직화하여, 데이터를 효율적으로 관리할 수 있게 한다.

데이터를 저장할 때 목적에 맞게 구조화하면, 주어진 문제를 더 `효율적`으로 해결하는데 큰 도움이 된다.

 

🔖 2) 알고리즘 성능 향상

자료구조는 다양한 알고리즘의 성능에 직접적인 영향을 미친다. 

일단 자료구조가 정해지면, 그 자료구조에 적용할 알고리즘은 상대적으로 명확해지기 마련이다.

예를 들어, 특정 데이터의 검색이나 삽입, 삭제와 같은 작업을 "잘 설계된" 자료구조로 "더 빠르게" 수행할 수 있다.

 

✒ 알고리즘(Algorithm)이란?

 

문제를 처리하는 절차를 뜻한다.

 

 

 

정리하자면, 효율적인 자료구조는 프로그램의 전반적인 성능을 향상 시킨다. 프로그램의 실행 속도, 메모리 사용량, 유지 보수성 등이 모두 자료구조의 선택에 따라 달라질 수 있으므로, 어떠한 경우든, 적절한 자료구조의 선택은 필수적이다.

 

 

 

 

 

📌 자료구조의 분류

자료구조는 크게 선형 자료구조와 비선형 자료구조로 분류된다.

• 선형 자료구조(Linear Data Structures) : 데이터가 순차적으로 배열된 구조이며, 각 요소는 이전 또는 다음 요소와 직접 연결되어 있다.
• 비선형 자료구조(Non-linear Data Structures) : 데이터가 계층적이거나 여러 갈래로 연결된 구조이며, 선형 구조와 다르게 복잡한 관계를 가질 수 있다.

선형 자료구조	배열 (Array)
	리스트 (List) / 배열 리스트 (Array List) / 연결 리스트 (Linked List)
	스택 (Stack)
	큐 (Queue)
	덱 (Deque)
비선형 자료구조	트리 (Tree) / 이진트리 (Binary Tree) / 힙 (Heap)
	그래프 (Graph)
	해시 테이블 (Hash Table)

 

 

🔎 해시 테이블은 선형일까? 비선형일까?

 

처음 공부할 때, 해시 기반 자료구조(예: 해시 테이블)의 분류에 대해 이해를 잘 못했었던 기억이 있다.

궁금해서 더 찾아봤더니 해시 테이블이 비선형 자료구조로 분류된 책이나 자료가 많이 보였다. 

 

"해시 테이블은 순차적인 연결로 이루어진 게 아니어서 선형 자료구조는 아니지만, 그렇다고 트리나 그래프처럼 계층적인 것도 아니지 않나?" 라는 의문이 들었다.

 

하지만 선형(Linear)이 아닌, 선형 이외의 자료구조들을 비선형(Non-linear)으로 구분 한다면, 해시 테이블도 비선형 자료구조로 불리는 게 맞다.

 

 

별것도 아닌데.. 혼자 오랫동안 심각하게 의문을 품었던 적이 있었다... 

 

 

 

 

 

🔖 1) 선형(Linear) 자료구조

선형 자료구조는 데이터를 순차적으로 배열하여 저장하는 구조를 말한다.

쉽게 말해, 한 줄로 차례차례 정렬된 데이터 구조라고 생각하면 된다.

 

각 요소는 이전 또는 다음 요소와 직접 연결되어 있다.

 

배열, 연결 리스트, 스택, 큐, 덱 등이 선형 자료구조에 속한다.

 

선형 자료구조의 예: 배열, 리스트

 

 

 

요소 간의 순서가 있다는 점이 선형 자료구조의 중요한 특징이기 때문에, 순차 접근(Sequential Access)과 무작위 접근(Random Access)이라는 개념을 명확하게 사용할 수 있다.

❕ 비선형 자료구조에서는 접근 방식을 구조(계층, 네트워크)에 따라 다르게 적용하는게 일반적이기 때문에 순차 접근이나 무작위 접근이라는 개념을 잘 사용하지 않는다.

 

✒ 순차 접근과 무작위 접근

 

순차 접근(Sequential Access)

: 데이터를 처음부터 순서대로 접근해야 한다.

예를 들어, 연결 리스트는 노드들이 포인터로 연결되어 있으므로, 특정 노드에 접근하려면 첫 번째 노드부터 시작해서 차례대로 이동해야 한다.

 

무작위 접근(Random Access)

: 특정 위치의 데이터에 바로 접근할 수 있다.

예를 들어, 배열은 메모리 상에서 연속적으로 저장되므로, 인덱스를 통해 특정 위치의 요소에 직접 접근할 수 있다.

 

 

 

🔖 2) 비선형(Non-linear) 자료구조

비선형 자료구조는 말 그대로, 선형 자료구조가 아닌 것들이다.

다르게 말해, 데이터가 계층적 또는 비순차적으로 연결된 구조를 말한다.

 

트리, 힙, 그래프, 해시 테이블 등이 비선형 자료구조에 속한다.

 

비선형 자료구조의 예: 트리, 그래프

 

 

비선형 자료구조는 데이터 간의 복잡한 관계를 자연스럽게 표현할 수 있어 다양한 문제를 해결하는 데 유용하다.

또, 계층적인 데이터 구조를 표현할 수 있어, 데이터의 계층적 관계를 명확하게 모델링할 수 있다는 장점이 있다.

 

---