Linked List - C와 Python 비교 - 개념

Linked List는 말 그대로 연결된 리스트를 말한다. 지금까지의 큐와 스택 등은 모두 배열 구조로 구현하였지만 이를 연결된 자료구조로 변환하겠다. 연결을 위해선 node의 구현이 필요하고 이 노드는 데이터와 함께 링크를 갖는다. 각 항목은 다음 노드를 가르키는 링크를 가져서 이를 연결시켜주면 되는 방식이다.

이 연결의 개념을 통해 더욱 복잡한 트리나 그래프와 같이 더 복잡한 구조도 효율적으로 표현할 수 있다. 또한, 용량이 고정되지 않아서 메모리를 효율적으로 활용할 수 있다. 또한, 중간에 자료를 삽입하거나 삭제하는 것이 용이하다.

하지만 이의 단점은 n번째 항목에 접근하는데의 시간복잡도는 O(n)이라는 것이다. 그리고 배열구조에 비해 상대적으로 구현이 어렵다는 점이다.(오류도 빈번)

연결리스트의 구조는 다음과 같다.

1. 노드: 데이터 필드와 함께 하나 이상의 링크 필드를 갖는다.

 - 데이터 필드 : 저장하고 싶은 데이터

- 링크 필드 : 다른 노드를 가리키는 즉, 다른 노드의 주소 저장 변수(C에서 pointer)

2. 헤드 포인터: 연결 리스트에서 첫번째 노드의 주소를 저장하는 변수

연결 리스트의 종류는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.

단순연결 리스트

출처: https://www.youtube.com/watch?v=C2sR5Z3V4H8

원형 연결 리스트

출처: https://meylady.tistory.com/6

이중연결리스트

출처: https://devbot.tistory.com/entry/3%EC%9E%A5-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%B4%EC%A4%91-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8

단순연결리스트는 하나의 방향으로만 연결되어 있는 구조를 갖는다. 따라서 링크는 하나이고 이 변수는 다음 노드의 주소를 기억하고 있다. 그리고 마지막 노드는 아무것도 연결되있지 않으므로 Null(None)값을 갖는다

원형연결리스트는 단순연결리스트와 동일한 노드 구조를 사용하지만 맨 마지막 노드의 링크 값이 Null(None)값이 아니라 다시 첫번째 노드의 값을 가르켜 순환하는 것이다. 

이중연결리스트는 단순연결리스트와 원형연결리스트와 달리 하나의 노드가 이전 노드(prev) 다음 노드 (next)를 모두 알고 있도록 설계되어 있다. 이중연결리스트는 선행 노드를 위한 링크가 있으면 어떤 노드에서 이전 노드를 바로 찾아갈 수 있다는 장점이 있다.