[Data Structure] 자료구조 : #1 선형구조

 

자료구조를 잘 이용하면

저장 공간을 효율적으로 이용하고, 신속하게 실행하는 효율적인 프로그램을 작성할 수 있다.

 

자료구조는 크게 아래와 같이 분류한다!

• 단순 구조
• 선형 구조
• 비선형 구조
• 파일 구조

 

그 중 '선형 구조'와 '비선형 구조'는

데이터를 연속적으로 연결하느냐, 비연속적으로 연결하느냐로 분류한다.

선형 구조와 비선형 구조에서 유의해야 할 특징에 대해 하나씩 정리해보려고 한다.

 

 

선형구조

 

배열 / 연속 리스트 (Contiguous List)  :  인덱스를 통한 데이터 접근, 데이터 삽입 / 삭제가 번거로움 (하지만, 밀도 1)

 

List[1] 과 List[2] 사이에 '3'을 추가하기 위해서 List[2], List[3]을 뒤로 한 칸씩 이동

다시 '3'을 제거하면 다시 List[3], List[4]가 앞으로 한 칸씩 이동

 

연결 리스트 (Linked List) :  중간 노드가 끊어지면,,,, 🤦🏻‍♂️🤦🏻‍♀️ ( +) 기억공간의 효율 ↓ / 접근 시간 ↑)

 

연속 리스트는 배열을 이용하기 때문에 연속되는 기억장소에 저장되어

논리적 순서와 물리적 순서가 동일하지만,

 

연결 리스트는 링크(포인터)를 이용해서 서로 연결시킨 자료구조로

논리적 순서와 물리적 순서가 다를 수 있다.

(즉, 반드시 연속적으로 배열시키지않음!)

 

배열에 비해 노드의 삽입 / 삭제가 용이하지만

1. 포인터의 부분(공간)이 추가로 필요  =>   기억공간의 이용 효율 ↓

2. 포인터를 찾는 시간이 필요      =>   접근 속도가 느림!

 

노드(Node) : 포인터는 다음 노드를 가르킴! 👉🏻

 

스택 (Stack) : First In Last Out (+) LIFO)

 

스택은 우리가 ctrl + z를 누르면 뒤로 돌아가는 것과 동일하다.

하나씩 요소를 뺄 수 있으며 가장 위의 요소만 접근이 가능하다.

(개인적으로 '프루팁스' 젤리가 생각났다,,,, ㅎㅎㅎㅎ)

 

 

큐 (Queue) : First In First Out,  Front 포인터 / Rear 포인터 

 

테이블로 표현하자면 대략 이런 형태이다.

터널에서 먼저 들어간 차가 먼저 빠져나가 듯! 먼저 들어온 요소가 가장 먼저 나간다.

 

데큐 (Deque) : 양방향 큐 

 

데큐는 De (Double End) + que 가 더해져

양방향에서 요소를 추가하거나 삭제할 수 있는 것을 의미한다.

 

큐와 스택이 합해진 형태로 볼 수 있다!

마지막으로 큐와 데큐는 데이터의 삽입/삭제가 빠르지만 중간에 위치한 요소에 접근하기 어렵다!

 

---

 

⚠️ 아래 내용은 모두 개인적인 참고 / 기록을 위한 용도입니다. 참고해주시고 편안하게 봐주세요 :)  ⚠️

***    혹시라도 잘못된 정보가 있다면  언제든지 알려주시면 감사하겠습니다  !    ***