200207_TIL (자료구조_Linked-List)

CS (Computer Science) 에서의 다양한 자료구조에 대해서 학습하는 스프린트를 진행중이다.

비전공자여서 자료구조가 뭔지.. CS가 뭔지도 몰랐어서 접근하는데 한참을 헤맨거 같다.

이번 스프린트를 통해서 객체지향 프로그래밍이 뭔지, 함수형 프로그래밍이 뭔지 조금은 감을 잡은 것 같다.

또한, 프로토타입 기반의 객체지향 프로그래밍 언어인 자바스크립트의 특성에 대한 이해가 조금은 되었다.

 

Linked-List

이번에 알아볼 자료구조는 Linked-List 이다.

자료구조 중 Queue 와 유사한 개념이라고 생각했기 때문에 굳이 Linked-List 라는 자료구조를 만들어낸 이유를 체감하지 못했다.

필요의 이유? 타당성을 짚고 넘어가야 개운하다는 생각에 한참 헤맸던 것 같다.

 

Linked-List 의 특성과 Queue 의 특성적인 차이는 마치 객체와 배열의 차이와 같다고 볼 수 있다.

처음 자바스크립트를 배울 때 배열을 다루기 시작한다. 배열은 인덱스 번호를 자동적으로 부여하는 정보의 모음이라고 볼 수 있는데, 배열을 사용하다보니, 새로운 값을 추가하고 싶을 때 앞이나 뒤라는 특정위치에만 추가가 가능했다.

'나는 한가운데에 정보를 넣고 싶은데...? 어떻게하지?' 라는 생각이 들었고, 배열의 일부를 slice하고 push하고 concat해서 원하는 결과를 만들어낼 수 있었다.

하지만! 객체를 배우고나니 인덱스 번호 대신, 프라퍼티라는 키값의 변화를 통해 내가 원하는 순서를 지정해서 객체안에 값을 담을 수 있었다. (물론 순서는 뒤죽박죽이지만...)

 

Queue는 배열과 유사한 것 같다. FIFO (First In First Out) 형식으로 중간에 누군가가 끼어들 수 없다.

(현실에선 새치기가 가능하지만, 컴퓨터는 정해진 프로세스를 거치기 때문에 새치기는 허용하지 않아!)

결국, 객체에서처럼 데이터를 중간에 끼워넣고, 중간에 있는 잘못된 혹은 쓸모없어진 데이터를 지워버리기 위해서는 다른 자료구조를 만들어내야 했던 것 같다. 뒤죽박죽인 순서대로 놔두면 자료를 찾는데 규칙성이 떨어지기 때문에 비효율적일 것이다.

그래서 만들어진 자료구조는 Queue 에서 틀을 제거하여 각 값들을 link 의 형태로 연결해버린 Linked-List :)

 

요런 식으로 이해했다.

 

따라서 Linked-List 를 구현할때 Linked-List 가 가져야하는 property 는 다음과 같다.

 

- Data field : Data 를 담아내는 부분

- Link field : 다음 노드와 link 를 담당하는 인식표 같은 부분

- Node : Data field 와 Link field 를 합쳐서 하나의 연결점이라는 개념으로 호칭

- Head : 모든 Data 의 시작점

- Tail : Linked-List 의 마지막 Data

 

그리고 Linked-List 를 구현할때 Linked-List 가 가져야하는 method 는 다음과 같다.

 

- append : link 되어있는 Data 의 끝에 새로운 Data 를 추가

- delete : 삭제하고 싶은 Data 를 삭제

- insert : 원하는 Data 를 중간에 삽입

- retrieve : 찾고 싶은 Data를 결과값으로 보여주는 명령어

 

마지막은 psudocode 를 작성해봐야... 하는데...

흐음....