1. Array and Linked List? (자료구조 기본_배열과 링크드리스트)

내가 이해하는 컴퓨터 프로그래밍은, 어떤 input 데이터를 넣고, 그것이 생각한 로직대로 Computing 되어 원하는 output을 얻을 수 있도록 코드를 효율적으로 짜는 일이라고 생각한다. 사실, Problem Solving 문제들을 처음 접했을 당시, C++에 있는 STL을 이용하여 이미 구현된 자료구조를 사용했기 때문에 내가 들여쓴 자료구조의 기본 원리에 대해서는 깊게 공부할 필요를 느끼지 못했다.(적어도 C++을 이용한 알고리즘 문제풀이를 놓고 봤을 때) ..이미 너무 구현이 잘되어있더라고.. 

이 프로그래밍에서, input 데이터를 '어떻게' 받을지가 중요하다. 문제에 따라 data를 받는 그릇을 최대한 효과적으로 선택해야 효율적으로(시간 복잡도 등을 줄이는 방식으로) 문제를 풀 수 있을 것이다. 데이터를 받는 그릇을 선택하고, 올바르게 사용하기 위해서 바로 자료구조가 필요한 것이라 생각한다. 컴퓨팅 자원이 한정적이니 최대한 상황에 맞는 자료구조를 선택하여 거기에 데이터를 담은 후, 가성비 좋게 문제 해결을 해야되지 않겠는가. 나아가 생각하면, 당장 돈이랑 연결되는 현실 문제를 해결한다는 점이 컴퓨터 공학 및 공학의 매력이고, 바로 이 점에서 공학이 자연과학과 분리된다고 생각한다. 

각설하고, Data Structure는 크게 Array와 Linked List로 생각해 볼 수 있다. 흔히 Problem Solving에서 Array는 많이 활용 되는 선형 Data Set이고, 동적 배열, 고정 배열(C++에서는 동적배열이 vector, 고정 배열은 배열의 크기를 미리 설정)로 용도에 맞게 구현한다. 두 번째로, Linked List는 서로 포인터로 연결이 되어 있는 자료 구조인데, 아래 그림을 참조하자. 

10이 데이터로 들어있는 Node는 Head, 30을 포함하는  Node는 Null을 가리킨다. 

각 Node들은 데이터를 담고 있는 그릇과, 다음 Node를 pointing하는 그릇을 갖고 있다. 이 원소를 pointing하는 것이 관건인데, 이 특성을 갖고 있기 때문에 Linked List를 이용해 소위 말하는 Stack, Queue, Tree등의 자료구조를 구현할 수 있는 것이다. 

이제부터 Linked List의 종류와 그 구현에 대해 포스팅으로 정리해보겠다. 최종적으로는 그 구현된 Linked List를 근간으로 Stack, Queue 등 Problem Solving를 위해서 사용하는 자료구조를 구현해볼 계획이다.