링크드 리스트

링크드 리스트란?

노드 라는 단위의 데이터를 저장하고

이처럼 데이터가 저장된 각 노드들을 순서대로 연결시켜 만든 자료구조이다.

노드라는 객체가 순서대로 저장된 것 처럼 보이나, 실제 메모리에서는 여기저기 흩어져 있다는 것을 기억하자.

 

각 노드에서 레퍼런스의 갯수를 기준으로 

싱글리 링크드 리스트와 더블리 링크드 리스트로 나뉜다.

 

이처럼 링크드 리스트는

데이터를 순서대로 저장해주는 자료구조이며

동적 배열과 같이 요소를 계속 추가할 수 있다 (구현 방식이 동적 배열보다 더 복잡하다)

주어진 상황에 따라 링크드 리스트 / 동적 배열 중 어느 자료구조를 적용하여 효율적으로 문제를 해결 할 수 있는지에 대한 감을 찾는것이 중요하다.

---

노드 (Node)

싱글리 링크드 리스트

각 노드는 하나의 객체로 표현되며 2가지 속성이 있다.

Data 속성은 저장하고 싶은 정보를 넣는다.

Next 속성은 다음 노드에 대한 레퍼런스이다.

---

더블리 링크드 리스트

각 노드는 하나의 객체로 표현되며 3가지 속성이 있다.

Prev 속성이 추가되며 이는 이전 노드에 대한 레퍼런스이다.

따라서 싱글리 링크드 리스트와는 다르게 이전의 노드에 대해서도 접근을 할 수 있다.

---

링크드 리스트의 head 와 Tail

링크드 리스트의 맨 앞에 위치한 노드를 Head 노드라 지칭하며 맨 뒤에 있는 노드를 Tail 노드라 지칭한다.

 

시간복잡도

싱글리 링크드 리스트

 

접근

인덱스 x에 있는 데이터에 접근하기 위해선 링크드 리스트의 head 노드로부터 x번 다음 노드를 찾아가야 한다.

따라서, 최악의 경우 O(n)의 시간 복잡도를 갖는다.

---

탐색

배열 탐색과 같은 방법으로 가장 앞 노드부터 찾아야하기 때문에 최악의 경우 O(n)이다. (선형탐색)

---

삽입/ 삭제

삽입과 삭제 연산의 경우 이론적으로는 주변 노드들의 레퍼런스만 변경하면 된다.

따라서 파라미터로 주어진 노드가 어떤 순서에 있는 노드든 상관없이 O(1)의 시간복잡도를 갖는다 할 수 있지만

현실적으로는 O(n)의 시간복잡도를 갖는다.

이유는 삽입/삭제 연산은 특정 노드를 넘겨주고 이 노드의 다음 순서에 데이터를 삽입/삭제하기 때문이다.

head/ tail 노드의 경우 항상 저장해주기 때문에 O(1)으로 찾을 수 있지만 나머지 노드들은 접근/탐색 연산을 통해 가져와야하기때문이다.

실제로는 O(n)의 시간 복잡도를 갖는다.

---

특수 연산

head와 tail 노드는 O(1)으로 노드의 갯수가 몇개이든 단번에 접근/탐색이 가능하며 head, tail 포인터를 재지정해주면 되므로 아래와 같은 시간 복잡도를 갖는다.

추가로, tail 노드를 삭제하기 위해서는 바로 전 노드가 필요하다. 

이 노드를 찾기 위해선 head 노드에서 n-2번 다음 노드로 접근해야하기때문에 O(n-2) 

즉, O(n)의 시간 복잡도를 갖는다

싱글리 링크드 리스트에서 가장 뒤 노드 삭제연산은 위 만큼 효율적으로 할 수 없다고 한다.

---

더블리 링크드 리스트

특수 연산을 제외하면 싱글리 링크드 리스트와 동일하다.

---

특수 연산

싱글리 링크드 리스트와 다르게 이전 노드에 접근할 필요가 없다.

더블리 링크드 리스트는 지우려는 노드 자체를 파마미터로 받기 때문에 한번에 삭제가 가능하다.

링크드 리스트를 사용해야하는 상황에서 tail 노드를 많이 삭제해야 한다면? =>

당연히 더블리 링크드 리스트가 성능면에서 효과적일 것이다.

---

추가적 공간

링크드 리스트에서는 실제 데이터를 저장하는 공간이 아닌 레퍼런스를 저장하는 공간을 추가적인 공간이라 표현한다.

두 자료형의 추가적 공간의 공간 복잡도는 O(n)으로 동일하기는 하지만 실제로는 2배 정도의 차이가 난다.

공간을 효율적으로 사용해야하는 상황에서는 싱글리 링크드 리스트를 사용하는게 효율적이다.

 

싱글리 링크드 리스트의 노드의 경우 노드가 n개 이면 레퍼런스의 개수는 n - 1을 차지한다.

 

더블리 링크드 리스트의 노드의 경우 노드가 n개 이면 레퍼런스의 개수는 2n - 2을 차지한다.

 

자료구조 기본기를 익히고 싶다면 굉장히 좋은 출발점이 될 강의로 생각한다.

출처 : 코드잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)

코딩이 처음이라면, 코드잇