230125 알고리즘, 자료구조: 배열, 연결리스트, 큐, 스택 편

✍️✍️✍️ 위 글은 작성자의 지식습득에 따라 추후 퇴고 될 수 있음을 알려드립니다(피드백 환영).

 

---

알고리즘/자료구조 두번째 시간.

배열과 연결리스트 라는 것을 배웠는데(딴 것도 더 배움),

내가 아는 배열의 개념과는 달랐다. 배운 내용과 함께 이해간 점들을 작성해 보려 한다.

 

---

출처: https://www.slideshare.net/alhazmy13/part1-overview-and-review

 

데이터 구조의 타입에는 여러가지가있다.

이번 시간에 배웠던 타입은, 배열(Array),  연결리스트(Linked List), 큐(Queue), 스택(Stack)

---

 

우선 그림에 나와있는 순서대로 배열과, 연결리스트에 대해 알아보자

 

배열, 연결리스트

1. 배열(Array)

내가 아는 배열이지만, 내용이 개념이 살짝 다르다는 점에서 놀랜 '배열' 자료구조타입.

 

배열이란,입력된 데이터들이 메모리 공간에서 연속적으로 저장된 자료구조이고, 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 때문에 메모리를 연속적으로 사용하지만, 인덱스를 통한 접근이 용이하다. 또한 배열의 크기는 처음 생성할 때 정해지고 그 이후에는 변경하기 어렵다.

 

---

2. 연결리스트(Linked List)

배열과 같으면서도 다른 연결리스트, 연속되어있지만 하나하나 연쇄적으로 연결되어있어 연결리스트라 불린다.

 

연결리스트란, 여러 개의 칸 같은 것들을 노드(Node)라 부르는데, 이 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다. 첫번째 노드를 head(머리), 마지막 노드를 tail(꼬리)이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(그림에 나온 화살표)로 이루어져 있다. 배열과는 달리 메모리를 연속적으로 사용하지 않는다.

순차적으로 접근해야 하는 면에서 비효율적이라 느낄 수도 있지만 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다(중간에 넣고 끊고 빼고 가능하단 소리).

 

Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

(트리는 다음시간에...!!)

+ 단일연결 리스트, 이중연결리스트도 다음글에 작성...!!

 

그래서 각각 배열과 연결 리스트는 아래와 같은 상황에서 사용할 때 유용하다

배열: 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적은 상황
연결 리스트: 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 상황

---

살짝 어려울 수도 있는 개념인 큐와 스택!

 

이 둘은 자료구조가 '큐' 혹은 '스택'으로 구분되기 위한 일종의 규칙이다.

이러한 애들을 추상적 자료 구조(ADT: Abstract Data Type)라 한다.

추상적 자료 구조는 자료구조의 한 형태인데, 자료구조의 방법이 코드로 정의 된 것이 아니라,

그 구조의 행동양식만 정의 된 것을 뜻한다. 그러니까 배열과 연결리스트와 달리

데이터가 어떻게 움직였는지(행동했는지)?를 알 수 있는 자료구조 라고(나는) 이해했다.

+ 큐와 스택은 위에서 설명한 배열에 어떤 '규칙'이 함께하는 것이라 보면 되겠다

 

큐, 스택

 3. 큐(Queue)

기다리는 버스 줄을 생각해 보며 이해해보자

 

버스 줄

줄 맨 앞에 있는 사람이 가장 먼저 버스를 타고, 가장 마지막에 기다린 사람은 당연히 맨 나중에 타게 된다.(뭐 물론 실제 탑승 시, 난장판인게 현실이지만서도..!!!)

가장 먼저 '큐'에 입장하게 된 요소가, 가장 먼저 큐에서 나오는 요소가 되는데 이를 FiFo(First in First out)라고도 한다.

 

새로운 요소는 '큐'의 맨 뒤에 추가가 되고, 맨 앞에 있는 요소만 읽거나 삭제 될 수 있다.

 

'큐'를 사용하는 예시로는 이메일 주고 받기 또는 푸시 알림 기능, 쇼핑몰의 주문순서(처음 주문한 사람이  가장 처음 배송 시작 알림 문자를 받는..!!)

---

4. 스택(Stack)

여러장 쌓인 팬케이크를 상상하며 스텍의 규칙을 이해해보자

데이터가 쌓인 스텍같은 팬케익

팬케이크가 쌓일 때 가장 최근의 팬케이크(최신데이터)가 가장 위로 올라오고,

이 쌓인 것들을 줄이고 싶을 땐 가장 위에있는 팬케이크를 먹어 치우게 된다(보통)

즉, 스택은

배열이 수직으로 쌓여 있다고 생각하면 된다.

위 배열에선 요소를 찾거나 추가 및 삭제 하고 싶을 때 가장 맨 위의 것 부터 진행하게 된다.

이러한 방식을 LiFo(Last in First out)라고 한다.

가장 나중에(최근에)쌓인 팬케이크가 가장 먼저 먹어치워진다(나가진다)라는 뜻.

 

그래서 뭐 우리 실 행동 중에 가장 와닿는 스택규칙은 '윈도우 창에서 뒤로가기'

가장 최근에 방문했던 웹사이트로 돌아가기 때문이다

ctrl+z or cmd+z도 마찬가지!! 가장 최근의 상태로 돌아가기 때문에 이것 또한 스택을 사용하는 예이다.

 

---

정리를 해보니 머리속에 뭐가 어떻게 돌아가는지 자리가 잡히긴했다. 

때문에 나중에 데이터가 사용되는 방법이라던가, 

동작하는 구조를 관찰? 할 때 아 이건 뭐구나, 이건 이걸로 동작하고있구나

라고 생각하면서 코딩을 할 수 있을 것 같다. 

다음글은 단일연결 리스트, 이중연결리스트 작성하기..!!!