Linked List

오늘 강사님께서 끝무렵 나태해진 학생들에게 따끔한 소리를 해 주시고, 마무리로 Linked List에 대하여 조사해오는 과제를 받았다.. 조사 결과를 5살 아이에게 설명하듯 설명해야 한다고 하셨다.

 

먼저 Linked List는 우리가 흔히 아는 배열과 다르다.

 

그렇다면 일단 먼저 배열의 특징을 알아보자. 배열은 메모리에 연속적으로 할당된 공간을 사용하여 데이터를 저장하는 자료구조이다. 

 

배열은 연속적이고, 고정적이라는 특징이 있다.

예시를 들자면, 집에 있는 책장에 책을 꽃는다고 가정해 보자. 

책장에 뭐... C언어책, JAVA 책, PYTHON 책을 꽂는다...

 

책장은 배열이고 책은 데이터라고 할 수 있다. 책장의 크기는 늘어나거나 줄어들지 않는다. 

 

즉 연속적이고 고정적이여서 순서가 명확하다. 내가 3번 위치 또는 1번 위치 등 접근하기 쉽다. 또한 빠르다.

 

하지만? 고정적이라는 한계점이 존재한다. 책장을 늘리고 싶다면? 1번과 3번 사이에 다른 책을 추가한다면? 

 

그런 기능들을 소화하기에는 부족하다. 그래서 유동적이고 삽입,삭제 등을 지원하는 List라는 자료구조를 사용하는것이다. 여러 List 중 Linked List라는 자료구조를 소개하자면 '연결된 리스트' 라고 할 수 있다.

 

순서도 없다. 크기도 없다. 데이터와 데이터 사이에 줄(연결)이 있다고 생각하면 된다.

 

배열은 자리(번호)가 있었다! 3번 자리 나와 하면 귤이 나오고 1번 자리 나와 하면 사과가 나온다.

 

LinkedList는 자리가 없다고 생각하면 된다!

대신 Node라는 개념이 있다. Node는 데이터와 다음 Node를 알고 있다.

 

즉 서로 연결된 데이터를 알고 있다.

 

사과는 배를 알고 배는 귤을 알고 귤은 자두를 안다.

이런식으로 Linked List의 특성으로 번호로 데이터를 찾는것이 아니라  Node를 타고 타고 가는것이다.

 

그렇다면 이점이 무엇일까? 아까 말했다시피 제일 강조되는것이 바로 삽입,삭제다. 먼저 배열에서 삽입,삭제를 해 보자면

 

2번째 데이터를 삭제한다고 해 보자.

이럴경우, 1과 3사이에 빈 공간(NULL) 이 생긴다.

 

연속적인 데이터를 위해서는 이 빈공간이 없어져야 하는데, 

배열에는 빈 공간을 없애는 기능이 없다.  따라서 이 작업을 진행하려면 

 

오른쪽에 있는 데이터를 왼쪽으로 이동시켜야 한다..  삽입 삭제 과정에서 이동이 많이 일어난다. 

 

데이터가 많을수록 더 많은 연산이 필요하다.

 

그래서 List를 사용하는 이유이다.

 

이제 Linked List에서 삽입, 삭제가 일어나는 과정을 보자면 다음과 같다. 

 

아까 첫 번째 그림을 다시 보자면.. 

 

노드라는것으로 서로 연결되어 있으니... 

사과와 배 사이에 데이터(수박)를 추가하면?

 

사과가 바라보는 노드를 배가 아니라 수박을 바라보면 되고 수박은 배를 바라보면 되는것이다.

이렇게 노드가 누구를 향하는지만 바꿔주면 Linked List에 데이터를 추가할수가 있다!

 

삭제도 동일하다. List에서 귤을 빼버리고 싶다면...

 

배가 바라보는 대상이 자두가 되게 하면 그게 삭제가 되는것이다! 

 

 

 

물리적으로 귤이 존재해도, Linked List 내부에는 귤을 바라보는 대상이 없으므로 귤은 List에서 더이상 접근할수가 없다.

 

어쨌든 .. 삽입 삭제에 용이하다!

 

이 원리에서 좀더 추가된 것이 있는데, 이중 연결 리스트라고 지금처럼 단방향이 아닌 양방향으로..

즉 앞 뒤가 존재하는 리스트다! 사과가 배를 알고 배가 사과를 알고..

 

Linked List에서 다음 노드를 알고 있어야 하는데 마지막 노드는 다음 노드가 없다. 그래서 마지막 노드의 다음 노드를 첫 번째 노드로 설정하면 그게 순환 구조가 된다.

이것을 5살 아이에게 설명해준다고 생각해보았는데.... 

짱구 과자가 생각났다.

 

짱구 과자를 실에다가 하나씩 끼워 넣는다고 생각하면 된다. 넣을수록 점점 쌓여간다. 이것이 배열이고 

 

마법의 실이 나타나서 실을 마음껏 붙였다 뗏다 할 수 있는게 Linked List...(죄송..) 

 

 

 

암튼 이런 개념이 있다... 이제 개념을 알았으니 직접 자료구조를 만들어보자.

 

먼저, Linked List에서 제일 중요한 Node라는 개념이 꼭 필요하다.

그래서 Node 클래스를 만들고 Node는 Value와 다음 Node를 알고 있다! 

배가 잘 출력된다.

 

데이터가 3개 있어도?

 

이런식으로 구성하면 된다.

 

이제 좀 더 큰 단위인 List를 만들기 위해 Link 클래스를 제작한다.

데이터(노드)를 무조건 알고 있어야 한다. 그래서 Node 변수를 하나 만든다.

역시나 다 아는것이 아니라 첫 번째 즉 머리와 끝 즉 꼬리를 알면 된다. 

 

그리고, 추가 기능을 구현하자면 데이터를 받고 그 데이터를 가진 노드를 생성한다. 그리고 그 노드를 끝(꼬리)로 설정한다. 

 

이제 데이터를 실제로 넣어보자면...

Good!

 

제가 구현한게 정확하게 맞는지는 모르겠으나 이러한 개념을 가지고 있다는점!

 

시간 관계상 여기까지..