자료구조(1) : 순차 자료구조와 선형 리스트

이글은 제가 쓰고싶은거 쓰는 글입니다.

 

오늘은 자료구조를 공부하였는데, 이 내용의 앞 내용들은 C언어의 문법적인 내용들이 많아, 이부분부터 공부를 시작하였다.

 

우선 내용을 설명하자면, 순차 자료구조란 논리적인 순서와 물리적인 순서가 동일한 자료구조를 의미한다.

이게 무슨말인지 봤더니, 논리적인 순서는 우리가 생각하고있고 우리가 표현할수있는 순서를 말하고, 물리적인 순서는 컴퓨터에 저장되는 데이터의 메모리상의 순서를 말한다.

 

그리고 순차자료구조와 비교되는 자료구조인 연결 자료구조가 있는데, 연결자료구조는 논리적인 순서와 물리적인 순서가 다른 자료구조를 특징으로 갖는다. 지금 이부분만 공부해서는 그럴수 있나 싶지만, 일단 이렇게만 알고있자. 

그리고 순차적인 특징을 갖으면서 그냥 원소를 순서대로 나열한 리스트(배열)가 선형 리스트이다. 선형 리스트는 우리가 흔히 알고있는 배열과 동일하다. 우리가 배열에 원소를 집어넣는 순서대로 메모리상에서도 순서대로 원소가 저장된다. 

예를 들어 리스트에 순서대로 1 2 3을 집어넣었다면, 메모리상에도 A , A+L , A+2L순서대로 저장된다.(A는 시작 메모리위치, L은 원소의 크기)

따라서 배열이 순차적인 특징을 갖고있음을 알수 있다. 

 

이렇게만 봣을때, 나는 공부하다가 의문이 들었다. 보기도 쉽고, 논리적인 순서와 물리적인 순서가 같아서 다루기도 쉬울거같은, 순차자료구조를 안쓰고, 뭣하러 힘들게 순서를 다르게 해서 쓰는가????

뭐 일단 공부하다 보면 알수 있겠지만, 우리는 연결 자료구조에 대해 알는게 없으니, 들어만 봐도 골치 아파지는 다음의 순차 자료구조의 한계를 보여주겠다.

 

10000명의 사람들이 줄을 서고있다 해보자. 이중 1000번째 사람이 줄에서 이탈하거나, 1000번째 자리에 새로운 사람이 새치기를 한다면 어떻게 될까??? 

 

물론 현실에서는 그냥 각각 한발자국씩 앞으로 혹은 뒤로 가면 되겠지만,(물론 새치기의 경우에는 응징을 가해야 한다.) 이게 배열상에서 생각해보자. 1000번째 요소를 삭제한다면, 그 빈공간을 그 뒤의 요소가 채워야 될것이고, 10000번째까지 이짓을 반복해야 한다.

딱봐도 힘들어 보인다. 새치기의 경우에도 1000번째를 먼저 비워야 하므로 10000번째부터 1000번째까지의 사람들을 뒤로 한칸씩 보내야 한다. 둘다 대충봐도 약 9000번정도의 이동횟수가 소모된다. 

 

이렇게 순차자료구조로 (일단은 리스트 한정이지만), 순서를 바꾸는것은 힘들다는걸 알았다. '그래서 연결 자료구조가 있나보다'라고 일단 생각하자. 

 

뭐 아무튼 선형 리스트의 구현에 대해 설명할건데, 힘들것도 없다. 그냥 배열이다. 배열에 순서대로 저장하면된다. 

이제 2차원 배열 3차원배열도 나오기는 하는데, 여기서 행,열,면 우선방식등이 나오는데, 이것들은 그냥 말장난으로 생각하자. 

arr[][]에서 행을 우선해서 셀것인가 열을 우선해서 순서를 정할것인가의 문제이기 때문에 걍 잊어버리고, 그때그때 우리에게 편한대로 자료구조를 만들면 될거같다.