처음 오는 곳이에요. 도와주세요! - Linked list

나는 오늘 처음으로 서울에 상경했다.

패스트파이브 성수점에 가고싶은데 지하철이랑 버스는 어떻게 타야할지 모르겠고.. 

저 많은 건물들 중 뭐가 패스트파이브인지 알아야 한단 말인가..

결국 길거리를 지나다니는 행인 분 들한테 물어보기로 했다.

여정

 

(강변역 도착)

     나    : 저기 혹시 패스트파이브가려면 어디로 가야하죠..?

행인 1 : 아 그 성수역에 있는거요? 그럼 일단 성수역에 가셔야 하는데, XX번 버스타시고 기사님한테 어디서 

               내려야 할지 물어보세요

 (버스 탑승)

      나       : 저 혹시 서울이 처음이라 그런데.. 성수역 가려면 어디서 내려야 하죠?

버스기사 : 3정거장 뒤에 내리세요~~

  (버스 하차)  

 나 : 저 혹시 패스트파이브가 어디에요?

행인 2 : 앞으로 쭉 걸어가다 보시면 될거에요!

  (패스트 파이브 도착)

  

1. Linked list(연결 리스트)란?

 위의 예를 기억하면서 Linked list의 개념을 살펴보자.

 Linked list는 Head와 Tail, 그 사이의 데이터들로 이루어진다. 

 Head는 데이터의 출발점이고, Tail은 데이터의 마지막 지점이고

 그 사이의 데이터들을 Node라고 칭하며, Node들은 배열처럼 시각적으로 이어진 데이터가 아니라

 떨어져 있는 데이터들이 서로 유기적으로 이어진 데이터이다.

 

 

2. 데이터들은 어떻게 이어질까?

 그럼 서로 각각 다른곳에 위치한 데이터들은 어떤식으로 이어질까?

 Linked list의 데이터들은 데이터와 주소값으로 이어진다.

 현재 데이터가 내가 찾던 데이터가 아니라면, 다음 데이터로 이동해서 탐색해야 하는데, 다음 데이터를 찾기 위해서는 주소값을 이용   한다. 

 

  

3. 그럼 데이터를 탐색하는데 느리지 않을까요?

 당연히 느리다.. 

  데이터는 다음 데이터에 대한 정보만 있기 때문에 탐색 자체는 느려질 수 밖에 없을 것 이다.

  총 4개의 데이터가 있을 때 Linked list의 방식으로 3번째 데이터를 찾기 위해서는 아래와 같은 그림과 같이 탐색이 이뤄질 것 이다.   

4. 그럼 어디에 좋은걸까..

 - 저장의 효율성(가변성)

  데이터들이 굳이 하나로 모여있을 필요가 없기 때문에, 주소값만 가지고 있다면 수 많은 데이터를 효율적으로 저장할 수 있다.

 

 - 삽입, 삭제, 조회의 자유로움

  Stack, Queue는 맨 처음과, 맨 마지막의 데이터만 삽입,삭제,조회 할 수 있다면, Linked list는 데이터들이 유기적으로 연결되어     있기 때문에 데이터 중간 중간에 데이터를 삭제하거나 삽입하거나, 원하는 데이터를 조회하는데 자유롭다.

 

5. 의사코드를 이용해 Linked list 의 기능 표현해보기

 1. head 

 // 맨처음 데이터 이기 때문에,  데이터 + 다음데이터의 주소값 으로 이루어지도록 구성

 

 2. tail 

 // 맨 마지막의 데이터 이기 때문에, 현재데이터주소 + 현재데이터 + Null 로 구성한다.

 

3. Node

// 데이터가 주소값을 통해 이어져야 하므로 현재데이터주소 + 현재데이터 + 다음 데이터 주소값으로 구성 

 

4.  삽입

// 1. 데이터를 어디에 삽입할지 결정한다.

// 2. 삽입할 곳의 앞 데이터의 다음데이터 주소값 에는 삽입할 데이터의 주소값을 덮어씌워준다.

// 3. 삽입할 곳의 뒷 데이터주소를 삽입하는 데이터의 다음데이터 주소값의 변수에 할당한다.

 

5. 삭제

//1. 삭제할 데이터를 결정한다.

//2. 삭제할 데이터 앞쪽에 위치한 다음 데이터의 현재데이터 주소값을 삭제할 데이터 뒷쪽의 데이터주소로 변경해준다.

 

6. 조회

//1. 조회할 데이터를 결정한다

//2. Head부터 시작해서 주소값을 타고 원하는 데이터를 찾을 때 까지 계속 반복해서 다음데이터로 이동한다.

//3. 만약 조회할 데이터를 찾았다면 true를 return 한다.