선형데이터구조, 연결리스트(LinkedList) #1 연결리스트 소개

1. 연결리스트(LinkedList)란 무엇인가?

배열과 비슷하게 연결리스트는 선형 데이터 구조입니다. 그러나 배열과는 달리 연결리스트의 요소들은 메모리상의 연속적인 위치에 저장되지 않습니다. 왜냐하면 요소들은 포인터를 사용하여 또 다른 요소의 주소를 가리키기 때문입니다.

 

2. 연결리스트를 사용하는 이유는 무엇인가?

연결리스트의 사용 이유를 설명하기 전에 배열의 단점을 설명하겠습니다.

1. 배열의 사이즈는 정적입니다. 그래서 사전에 저장하는 공간을 배열로 사용할때 배열의 크기를 먼저 정해야 합니다. 그리고 크기의 상한선을 미리 정한다면 메모리 위에서도 배열은 그 크기만큼 공간을 사용하고 있을 것입니다.
2. 배열에서 새로운 요소를 삽입하는 것은 비용이 많이 소모됩니다. 왜나하면 배열에 요소를 삽입시 배열 내에서 순서를 유지하기 위해서 요소들의 이동이 요구되기 때문입니다. 예를 들어 아래와 같은 배열이 존재한다고 할때 0번째 자리에 1005 요소를 삽입한다고 했을때 1000이후의 요소들은 오른쪽으로 한칸씩 이동해야 합니다. 이러한 단점은 삭제시에도 적용됩니다. 다시 0번째 요소를 삭제한다고 할때 1010 이후의 요소들은 왼쪽으로 한칸씩 이동해야 합니다.

id[] = [1000, 1010, 1050, 2000, 2040]
insert(0,1005)
id[] = [1005, 1000, 1010, 1050, 2000, 2040]
delete(0,1005)
id[] = [1000, 1010, 1050, 2000, 2040]

 

3. 연결리스트의 장점

1. 동적인 크기, 배열과는 달리 크기를 정하지 않아도 됩니다.
2. 삽입과 삭제가 쉽고 비용이 낮습니다.

4. 연결리스트의 단점

1. 랜덤 엑세스(Random Access)를 허용하지 않습니다. 우리는 첫번째 노드부터 시작하여 순차적으로 요소들에게 접근해야합니다. 따라서 기본적인 구현으로는 연결 리스트를 사용하여 이진 탐색같은 것을 효율적으로 수행할 수 없습니다.
2. 다음 노드를 가리키기 위한 포인터의 추가적인 메모리 공간이 요구됩니다.
3. 캐시를 사용하지 않습니다. 배열의 요소들은 연속적인 위치에 존재하기 때문에 참조 지역성의 원리가 존재합니다. 그러나 연결리스트는 존재하지 않습니다.

 

References

https://www.geeksforgeeks.org/linked-list-set-1-introduction/