[자료구조] 링크드리스트(Linked List)

[자료구조] 링크드리스트(Linked List)

기존 배열은 맨 앞에 요소를 삭제하게 되면 다른 요소들을 한칸씩 앞으로 땡겨야 하는 단점을 가지고 있습니다.

심지어 생성할 때 크기도 설정해 주어야 하죠. JS에서는 아닙니다만..

이런 문제를 해결하기 위해 나온 자료구조가 바로 링크드리스트입니다!

목차

0. 링크드리스트?

링크드리스트란 이름 그대로 Link로 연결된 List 를 의미합니다.

도대체 링크로 연결하는 것이 일반 배열과 무슨 차이가 있냐?? 라고 말씀하실 수 있을 것 같아서 이해를 돕기 위한 사진 하나를 가져왔습니다.

출처 : 오픈튜토리얼즈 https://opentutorials.org/module/1335/8821

위 사진을 보시면, 데이터들이 줄줄이 연결되어 있는 것 을 보실 수 있습니다.

이렇게 데이터끼리 서로 연관성을 가지고 연결이 되어있는 형태의 자료구조를 Linked List라고 부릅니다.

데이터의 시작 부분에는 HEAD라는 포인터 변수가 하나 존재합니다. (포인터 변수를 잘 모르셔도 Linked List의 이해에는 크게 문제가 없습니다!!만 알면 더 좋겠죠? ^^)

HEAD는 첫 번째 데이터의 위치를 나타내는 편의를 위해 존재하는 더미라고 생각하면 됩니다!

이제 Data Field와 Link Field가 보입니다. 각각 데이터를 담는 구역 과 다음 데이터를 나타내는 포인터를 담는 구역 이라고 생각하시면 됩니다!

그리고 두 요소를 묶어서 하나의 노드, 혹은 Node Vertex라고 부릅니다.

다시 복습하면, 각 노드들은 순서대로 Link Field로 연결되어있는 구조 라고 생각하시면 됩니다.

1. 요소 추가와 삭제

Linked List의 가장 큰 장점이 바로 요소를 추가하고 삭제할 때 배열처럼 데이터의 위치를 변경하는 일을 하지 않아도 된다는 것 입니다.

이 장점으로 인해서 요소 추가와 삭제시 시간복잡도 를 O(N)에서 O(1)로 획기적으로 줄일 수 있게 되었습니다.

또한 Linked List를 통해 List의 크기를 동적으로 설정 할 수 있게 된 것이죠!

좀 많이 조악하지만.. Linked List에서 요소 추가와 삭제를 하게 되면 어떻게 동작하는지를 그림판을 이용해서 그려보았습니다.

왼쪽 : 요소 추가 / 오른쪽 : 요소 삭제

그림은 왼쪽이 요소 추가, 오른쪽이 요소 삭제를 나타냅니다.

새로운 요소를 추가하게 되면 새로운 노드가 하나 생성되고, 그 노드 안에는 데이터(Data Field)와 다음 요소를 가리키는 포인터 정보(Link Field)가 들어가게 됩니다.

새롭게 추가된 친구는 들어갈 위치를 찾게 되면 앞 노드의 Link Field를 새로 생성한 노드의 주소 로 바꾸고, 새로 생성한 노드의 Link Field는 뒤 노드의 주소 로 설정하기만 하면 끝입니다.

삭제도 비슷한 메커니즘입니다.

임의의 포인터변수를 하나 만들어서 삭제할 노드를 가리킵니다. (삭제 전에 이 작업을 하지 않으면 해당 노드가 메모리에서 붕 뜨게 되는 memory leak 현상 이 발생합니다!)

그리고 삭제할 노드의 앞 노드의 Link Field를 삭제할 노드 다음 노드의 주소로 바꿔줍니다.

마지막으로 삭제할 노드를 가리키는 tempPtr을 delete해 주는 방식으로 메모리에서 해제합니다.

아래는 C++로 구현한 링크드리스트의 요소 추가와 삭제 입니다. (링크드리스트로 만든 스택이기 때문에 Push와 Pop을 하게 되면 top 위치에 있는 요소만 변경됩니다!)

왼쪽 : 요소 추가 / 오른쪽 : 요소 삭제

2. 링크드리스트의 한계 돌파

하지만 이런 링크드리스트도 한계가 있습니다.

엄밀히 말하면 지금까지 위에서 구현한 내용은 Singly Linked List입니다.

왜냐면 한쪽 방향으로만 가리키고 있기 때문인데요!

이런 구현 방식은 내 뒤에 있는 노드가 아닌 앞에 있는 노드를 확인하고 싶을 때 문제가 발생하게 됩니다.

다시 돌아갈 수 있는 방법이 없는 것이죠.

그래서 처음 등장하게 된 것이 바로 Circular Linked List입니다.

Circular Linked List는 말 그대로 순환하는 Linked List입니다.

맨 뒤 노드를 맨 앞 노드와 연결 만 해주면 되므로 구현이 간편합니다.

다만 한칸 뒤로 가기 위해 한바퀴를 다 돌아야 한다는 단점이 있습니다.

그렇다면 그냥 단순히 앞으로 가는 경로를 하나 더 만들어주면 되지 않을까요?

그래서 등장한 방법이 바로 Doubly Linked List입니다.

Doubly Linked List는 앞으로 이동하면서 탐색이 가능 하다는 장점이 있습니다.

상황에 따라 탐색의 방향이 바뀌어야 할 경우 유용합니다.

하지만 단점이 없는 것은 아닙니다.

또 하나의 Link Field가 필요하기 때문에 추가적인 메모리가 필요하고, 구현이 조금 더 복잡합니다.

이런 단점에도 불구하고 현실에서 사용하는 연결리스트의 대부분은 Doubly Linked List로 구성되어있다고 합니다!!

반응형

from http://ssocoit.tistory.com/229 by ccl(A) rewrite - 2021-12-15 03:01:15