기존 배열은 맨 앞에 요소를 삭제하게 되면 다른 요소들을 한칸씩 앞으로 땡겨야 하는 단점을 가지고 있습니다.
심지어 생성할 때 크기도 설정해 주어야 하죠. JS에서는 아닙니다만..
이런 문제를 해결하기 위해 나온 자료구조가 바로 링크드리스트입니다!
목차
0. 링크드리스트?
링크드리스트란 이름 그대로 Link로 연결된 List를 의미합니다.
도대체 링크로 연결하는 것이 일반 배열과 무슨 차이가 있냐?? 라고 말씀하실 수 있을 것 같아서 이해를 돕기 위한 사진 하나를 가져왔습니다.
위 사진을 보시면, 데이터들이 줄줄이 연결되어 있는 것을 보실 수 있습니다.
이렇게 데이터끼리 서로 연관성을 가지고 연결이 되어있는 형태의 자료구조를 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로 구성되어있다고 합니다!!
최근댓글