[자료구조] 선형구조와 비선형구조

🐣 자료구조의 선형 구조와 비선형 구조

---

 1학기 자료구조 강의와 정보처리기사를 준비하면서 자료 구조 그 중 선형구조와 비선형구조에 대해서도 살펴보게 되었다. 그래도 한번 정리하고 가는 것이 나중을 위해서도 편할 것 같아서 끄적끄적 적어본다. 새삼 느끼는 거지만 비전공자는 스스로 찾아서 공부 하는 습관을 길들여야 하는 것 같다. 떠먹여 주지 않으니 하나씩 차근차근! 나아가보자!

 

🐣 자료구조

---

1. 자료구조의 개념

• 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조
• 자료 구조의 현명한 선택을 통하여 효율적 알고리즘을 사용할 수 있게 하여 성능을 향상시킴

2. 자료 구조의 분류

자료 구조는 선형 구조와 비선형 구조로 크게 나뉘는 것을 확인할 수 있음

 

구조	설명	종류
선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스택, 큐, 데크
비선형 구조	데이터를 비연속적으로 연결한 자료 구조	트리, 그래프

 

• 아래의 그림을 통해 쉽게 파악해보자

https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FLndbj%2FbtqSa9FxX1x%2FrmBM8kJTQIrFzRYs6aPFGK%2Fimg.png

 

 

🐣 선형 구조

---

1. 개념

선형 구조는 데이터를 비연속적으로 연결한 자료 구조

 

선형 데이터 구조에서 데이터 요소는 순차적 순서로 배열되며, 각 요소는 이전 및 다음 인접 요소에 연결. 이 구조를 사용하면 데이터를 직접 탐색할 수 있음. 삽입, 삭제, 액세스와 같은 일반적인 작업은 일반적으로 순차적으로 수행.

 

2. 종류

  2-1. 리스트

  선형 리스트(Linear List)

   단일 연결(각 노드가 다음 노드를 가리킴) 또는 이중 연결(각 노드가 다음 노드와 이전 노드를 모두 가리킴)일 수 있음

 

  연결 리스트(Linked List)

   각 노드가 데이터와 다음 노드에 대한 참조(또는 링크)를 포함하는 일련의 노드

 

자세한 개념?
선형리스트, 연결리스트  - 해당 개념은 아래 정리글을 참고!

 

  2-2. 스택 stack

한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In First-Out) 후입 선출 형식의 자료 구조

 

  2-3. 큐 Queue

한 쪽 끝에서는 삽입, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(First-In First-Out) 형식의 자료 구조

 

  2-4. 데크 Deque

큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조

 

자세한 개념?
스택,큐,데크 - 해당 개념은 아래 정리글을 참고!

 

🐣 비선형 구조

---

1. 개념

비선형 구조는 데이터를 연속적으로 연결한 자료 구조

 

비선형 데이터 구조에서는 데이터 요소가 순차적으로 배열되지 않음. 대신 계층적이거나 상호 연결된 방식으로 배열되어 요소 간에 복잡한 관계를 형성 가능함. 순회는 선형 구조에 비해 더 복잡할 수 있음

 

2. 종류

  2-1. 트리 Tree

트리는 데이터들을 계층화시킨 자료 구조로 그래프의 특수한 형태이다. 노드(node)와 선분(branch)으로 이루어져 있고, 정점 사이에 사이클(Cycle)이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조

 

  2-2. 그래프 Graph

그래프는 노드(Node)와 노드를 연결하는 간선(Edge)을 하나로 모아 놓은 자료 구조

 

자세한 개념?
트리와 그래프- 해당 개념은 아래 정리글을 참고!

 

🐣 선형 구조 vs 비선형 구조

---

1. 메모리 활용

선형 구조

연속된 메모리 위치를 사용하는 경우가 많아 공간을 효율적으로 사용

 

비선형 구조

더 복잡한 메모리 관리가 필요할 수 있으며 포인터를 사용하는 경우가 많아 오버헤드가 발생할 수 있

 

2. 복잡성

선형 구조

일반적으로 구현하고 이해하기가 더 쉬움

 

비선형 구조

더 복잡한 관계를 나타낼 수 있으며 고급 응용 프로그램에서 자주 사용

 

3. 순회

선형 구조

탐색이 간단

 

비선형 구조

비선형 구조의 순회는 더 복잡할 수 있으며 특수 알고리즘(예: 순차, 사전 순서, 사후 순서와 같은 트리 순회 알고리즘)이 필요할 수 있

 

4. 삽입, 삭제

선형 구조

요소를 이동해야 하기 때문에(특히 배열에서) 이러한 작업에 시간이 더 많이 걸릴 수 있음

 

비선형 구조

삽입과 삭제가 더 효율적일 수 있지만 포인터나 참조를 처리해야 함

 

---

선형구조와 비선형구조의 개념과 종류들에 대해서 살펴보았다. 각각의 자세한 개념들은 따로 게시글로 정리해 링크를 걸어놨으니 참고하기 🤓🤖🌼

---

하나둘씩 나아가다 보면 ! _ !

 

[자료구조] 선형 리스트(Linear List)와 연결 리스트(Linked List)