자료구조
자료를 책이라고 한다면, 자료구조는 책의 나열 방법이다. 만약 큰 서점에서 책을 아무렇게나 나열하면 어떻게 될까? 아마 어떤 책을 찾는데, 엄청 많은 시간이 걸릴 것이다. 그러나 규칙에 따라 나열하면, 찾기도 쉽다.
자료구조도 마찬가진데, 검색을 용이하게 하기위해서 일정 규칙으로 나열하는 것이다. 그래서 컴퓨터의 자료를 효율적으로 관리, 구조화하는 것이 목적인 내용이다.(사실 강의에서는 자료구조를 자세히 다루지 않으니, 추가로 배우자하면 자료구조와 관련된 책을 읽는 것이 좋다.) 주로 자료구조는 정렬, 검색, 인덱스 처리, 파일편성 같은 것에서 효율을 필요로 할 때 쓰인다.
선형, 비선형
자료구조는 크게 선형과 비선형, 2가지로 나뉜다. 선형에는 Stack(스택), Queue(큐), Deque(데큐)가 있다. 그리고 비선형 자료는 Tree(트리)라고 통틀어 볼 수 있다.
이들의 공통분모는, 지난 시간 배운 Node(모드)다. 모드는 자료구조의 공통되는 덩어리인데, 이것이 어떤 구조로 쓰이냐에 따라서 선형과 비선형으로 나뉘는 것이다. (비선형인 Tree(트리)로 쓰이면 더욱 복잡해진다.)
여기서 배울 것은 자료구조 중 선형구조인데, 이것을 Node(모드)로 어떻게 구현하느냐에 달렸다. 그때의 구현하는 방법은 지난시간 강조됐던, ‘자기참조 구조체‘다.
선형 자료구조
김치냉장고를 보면, 아래서부터 차곡차곡 쌓여서, 맨 아래의 통을 꺼내려면, 위에 쌓인 것부터 모두 빼야 된다. 이것이 Stack(스택)자료구조다. 전에 이미 자주 다룬 자료구조다. 그 내용에서 보충하자면, 자료를 넣는 것을 다른 말로 Push(푸쉬), 꺼내는 것을 Pop(팝)이라고 한다. (스택은 이 입출구가 하나로 통일 돼있다.)
여기서 Queue(큐)는 김치냉장고 아래에 구멍을 뚫어서, 입력(푸쉬)와 출력(팝)을 따로 따로 분리하는 것이다. 그래서 큐의 구조가 줄 세우기다. (입구와 출구가 분리돼 있어서, 자료가 입구 -> 출구 방향을 띈다.) 대기 열이나, 그 외의 것들이 모두 큐와 같기에, 스택보다도 많이 쓰이는 자료구조면서, 이 큐가 바로 연결 리스트다.
Depue(데큐)는 양쪽에서 입출력을 할 수 있는 자료구조다. 그래서 스택을 두 개 붙인 걸로도 활용할 수 있다. 아니면, 큐의 방향을 양쪽으로 할 수 있는 유용한 자료구조다.
연결 리스트(Linked List)
배열과는 다르게, 데이터를 추가, 삭제할 수 있는 것이, 연결 리스트라 할 수 있다.
배열은 한번 메모리를 확보하면 변경할 수가 없다. 그러나 연결리스트는, 중간에 데이터를 마음대로 변경할 수 있다. 대신에 구현하기는 배열보다 어렵긴 하다.
열결 리스트는 지난강의의, ‘자기참조 구조체‘를 생각하면 된다. 지난시간의 연결리스트처럼, 연결고리를 포인터로 하는 것이 핵심이다. 그중, 포인터가 1개로 하나로 연결되어있는 것을 ’단일 연결 리스트’라고 한다.
예제, 전체 접근 코드
꼭 영상에서도 이 예제를 강조했듯이, 예제를 정확히 이해하자. 우선 기본으로 구조체를 왼쪽 그림과 같이 만들어 줬다. 유 모드(Node), 박 모드(Node), 노 모드(Node)가 구조체의 맴버인 포인터로 이렇게 가리키고 있게 말이다. 추가로 pTmp도 유 모드를 가리키는 상황이다.
진짜 핵심은 여기부터다. 후에 붙는 while문인데, 오른쪽 그림같이 while문이 pTmp가 널 문자가 아닐 때까지 반복되는데, 그 실행문이 pTmp가 가리키는 pNext의 값을 pTmp에 집어넣는 것이다. 이걸 이해하면 끝이다.
pTmp가 처음에는 유 모드를 가리키니까, 유 모드의 pNext의 값이 대입된다, 그후에는 pTmp가 유 모드의 pNext값과 같게 돼서, 박 모드의 pNext를 가리키게 된다.
이것이 노 모드까지 가서, pTmp가 노 모드의 pNext값인 널 문자가 될 때까지, 모든 모드가 printf로 출력되는 것이다. 이것이 가장 중요한, ‘전체 접근 코드‘다.
이것을 puts로 활용하면 puts(pTmp->szName); puts(pTmp->pNext->szName);
puts(pTmp->pNext->pNext->szName); 과 같이 해도, 위와 같은 출력결과를 볼 수 있다. (사실 굳이 이렇게 puts에서 여러 번 맴버접근을 할 필요는 없지만, 개념 이해를 목적으로 적은 것이니 그런가하고 넘어가자.)
