링크드 리스트에 정확한 개념

링크드 리스트를 많이 들어봤는데 정확한 개념을 모르겠습니다.

 

삼국지 게임에서요

 

도시들이 각각 분포 되 있잖아여...

 

지도가 대략

 

 

영창  천수 

 

북평

 

진양

 

이렇게 있으면요...

 

진양에서 천수로 가는길은 진양 => 북평 => 영창 => 천수인데요..

여기서 진양에서 바로 천수로 못가게 만드는것이 링크드 리스트인가요?

그러니깐 인접 리스트말이죠?  인접한곳만 거쳐서 간다.. 이 개념이 링크드 리스트인가요?

링크드 리스트와 유사하면서 비교되는 개념이 배열이랍니다.

일딴 배열이 무엇 인지는 아시겠죠.

배열은 같은 자료형을 여러개 사용할때 유용하게 쓸수 있겠죠.

그러나 그 같은 자료형들이 몇개가 생길지 예상을 못하거나 너무 가변적일때가 있잖아요.

 

예를 들어 학생 데이터를 배열로 잡았을 경우,

학생이 30명 정도인데 적어도 100명은 안 넘을 것이다고 배열을 100개를 할당한다면

70명 분은 '낭비' 가 생기는 거죠.

 

링크드 리스트라는 것은 주로 일자로 연결하여 순차적으로 접근해서 모든 자료를

접근 할 수 있게 하면서 크기를 동적으로 늘였다 줄였다 할 수 있는 것입니다.

 

따라서 링크드 리스트와 배열과의 차이점은

링크드 리스트는 크기를 동적으로 할당하여 메모리 낭비를 막는 개념이고

배열은 크기를 정적으로 할당하므로 주로 크기가 한정되거나 거의 변화가 없는 부분에서 많이 사용합니다.

(여기서 배열도 동적으로 생성 가능하다고 태클 하실 분이 많으실텐데.. 중간에 삽입될때를 생각하셔서 태클을 자제 좀.. ^^)

대신 링크드 리스트는 임의접근이 거의 불가능하고 배열은 임의접근이 가능하죠.

이 말은 100개의 데이터 중에서 50번째 데이터를 접근하려고 할때

링크드 리스트는 첫번째부터 링크를 따라 50번을 가야 원하는 데이터에 접근을 할수 있는데 배열은 array[49] 이렇게 인덱스를 이용하여 단 한번에 접근이 가능하지요.

그러므로 그 성격에 맞게 링크드 리스트와 배열을 선택해서 사용하는게 중요합니다.

 

 

님께서 질문하신 부분은 그래프 개념에서 나온것으로 추측되는데

그래프를 데이터로 나타낼때 배열이나 링크드 리스트를 이용한 개념을

자료구조나 알고리즘 책에서 주로 다룹니다.

 

예를 들어서

ⓞ

│ 

①─②──③─④

│   └⑤   │

⑥      │   ⑦

         ⑧─⑨

이런 길이 있다고 합니다.

줄로 연결 되어 있는 부분이 님께서 말씀하신 삼국지의 길이라고 한다면

배열로 나타낼 경우에는

 

   0 1 2 3 4 5 6 7 8 9

0 - 0 - - - - - - - -

1 0 - 0 - - - 0 - - -

2 - 0 - 0 - 0 - - - -

3 - - 0 - 0 - - 0 - -

4 - - - 0 - - - - - -

5 - - 0 - - - - - 0 -

6 - 0 - - - - - - - -

7 - - - 0 - - - - - -

8 - - - - - 0 - - - 0

9 - - - - - - - - 0 -

 

첫칸과 첫줄은 이중배열 인덱스를 나타냅니다.

이런식으로 0번과 1번이 연결 되어 있으므로 a[0][1], a[1][0] 에 연결 되어 있다는 체크를 합니다.

보통 1과 0으로 표시하지만 보기 쉽게 "0"이 연결 되어 있는 것이고 "-"가 연결이 안된 부분 입니다.

저렇게 하면 100개의 저장 공간이 필요합니다.

즉 도시개수의 제곱만큼의 공간이 필요하다는 것이죠.

 

 

링크드 리스트의 경우에 표현 하는 방식은

ⓞ

│ 

①─②──③─④

│   └⑤   │

⑥      │   ⑦

         ⑧─⑨

0->1

1->0->2->6

2->1->3->5

3->2->4->7

4->3

5->2->8

6->1

7->3

8->5->9

9->8

이렇게 표현합니다. 맨 앞에 있는 숫자는 보통 배열로 잡습니다.

그러면 a[10]크기의 배열과 노드가 18개이므로 28개의 저장공간이 필요하니

같은 내용을 표시하는데 72개의 공간이 절약이 됩니다.

(물론 포인터공간은 셈하지 않았습니다. 그러나 데이터의 크기가 크다면

포인터의 크기는 무시할 수 있습니다.)

 

 

따라서

진양에서 천수로 가는길은 진양 => 북평 => 영창 => 천수인데요..

이건 그래프를 링크드 리스트로 표현한것으로 보기 힘들고

그래프를 링크드 리스트로 표현한다면

진양에 인접한 도시들이 옆에 붙게 됩니다.

만약 이 그래프에서

ⓞ

│ 

①─②──③─④

│   └⑤   │

⑥      │   ⑦

         ⑧─⑨

0번이 천수쯤 될테고 3번을 진양으로 본다면

링크드 리스트 구조에서 찾아 볼때 3번에서 0번으로 가는 길을 찾기 위해서

0->1

1->0->2->6

2->1->3->5

3->2->4->7

4->3

5->2->8

6->1

7->3

8->5->9

9->8

3번에 연결되어 있는 2, 4, 7번으로 갑니다. 원래는 다 방문해서 가봐야 하는데

우리는 눈에 길이 보이니까 ^^; 2번으로 갑시다.

그럼 2번에 연결 되어 있는 1, 3, 5번이 있는데 역시 1번으로 가죠.

그럼 1번에 연결된 도시는 0, 2, 6번으로 0번으로 갈 수 있는거죠.

따라서 3번과 0번은 같은 그래프 안에 있다고 할 수 있습니다.

(가는 길이 있다는 말이죠.)

이런 식으로 표현을 합니다.

 

이렇게 보면 배열로 나타낸 그래프가 너무 초라해 지는것 같아서 좀 덧 붙이자면

다루기 쉬운걸로 보면 링크드 리스트는 배열을 따라갈 수가 없겠죠.