[링크드 리스트] 링크드 리스트 정리

1. 링크드 리스트

- 배열과 같이 데이터를 순서대로 저장해주는 자료 구조다.

- 각 노드가 다음 노드에 대한 레퍼런스만 저장하는지, 아니면 다음과 전 노드에 대한 레퍼런스를 모두 저장하는지에 따라 싱글리 링크드 리스트와 더블리 링크드 리스트로 구별할 수 있다.

- 링크드 리스트 노드들은 메모리에 연속적이거나 순서대로 저장되지는 않는다. 메모리 이곳저곳 아무 데나 저장돼 있을 수 있다.

- 싱글리 링크드 리스트는 처음에 크기를 정하지 않아도 그냥 새로운 노드를 만들어서 기존 노드들에 연결만 시켜주면 계속해서 새로운 데이터를 더해줄 수 있다.

- 파이썬에서는 노드 클래스를 정의하고, 인스턴스들을 만들어서 연결하면 링크드 리스트를 구현할 수 있다.

 

2. 싱글리 링크드 리스트와 더블리 링크드 리스트 연산

- 싱글리 링크드 리스트의 tail 노드를 삭제하려면 tail 노드 전 노드에 접근해서 tail 노드를 삭제하는 데 총 O(n)의 시간이 걸린다.

- 더블리 링크드 리스트는 맨 앞과 맨 뒤에 삽입이나 삭제하는 4 개의 연산들을 모두 O(1)으로 할 수 있다.

- 싱글리와 더블리 링크드 리스트 일반적인 경우의 삽입 삭제 연산들은 파라미터로 노드를 받는다. 이 노드를 가지고 있으면 삽입과 삭제 연산을 O(1)으로 할 수 있다. 하지만 실질적으로는 이 노드를 가지고 오는데 최악의 경우 O(n)이 걸린다. 그러니까 필요한 노드를 가지고 온 후, 삽입 삭제 연산들을 하는 총 시간을 따지고 보면 O(n)이 걸리는 셈이다.

 

필요한 노드를 한번에 바로 가지고 올 수 있는 경우나, 이미 필요한 노드를 가지고 있는 경우를 제외하고는 동적 배열보다 항상 효율적이라고 할 수는 없다.

- 링크드 리스트의 탐색 연산은 동적 배열과 같이 처음부터 끝까지 모든 데이터를 하나씩 보는 선형 탐색 방법을 쓴다.

- 가장 앞 순서에 데이터를 많이 삽입해야 되는 경우에는 싱글리 링크드 리스트가 동적 배열보다 더 효율적이다.

 

3. 더블리 링크드 리스트 대신 싱글리 리스트를 사용하는 것이 좋은 경우

- 프로그램이 너무나도 많은 메모리 공간을 사용할 것 같기 때문에 공간을 좀 더 효율적으로 사용하고 싶은 경우.

 

4. 더블리 링크드 리스트를 사용하는게 다른 경우들보다 비효율적인 경우

- 게임 캐릭터들의 순위 정보를 더블리 링크드 리스트에 저장해 놓고 이 순서를 이용해서 데이터에 접근해야될 때.