[자료구조] 7강 1-2절 연결리스트의 필요성 ~ 단순 연결 리스트

연결 리스트의 필요성

 

순서 리스트는 배열을 이용하여 구현 -> 메모리 사용 측면에서의 비효율적인 문제점이 나타난다.

순서리스트에서 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간이 소요되는 점이 가장 큰 부담

-> 따라서 순서리스트에서 나타나는 문제점을 개선할 자료표현방법이 필요

 

순서리스트에서 원소의 삽입과 삭제시 빈번한 자리이동으로 복잡도가 증가하고 부담이 증가.

이미 사용중인 크기를 변경하고자 하는 경우에는 연속적인 공간의 여유가 있는 경우에서는 문제가 되지 않지만 사용 중인 공간 이후에 여유 공간이 부족하면 기억공간에서 확장할 크기를 포함하는 기억 공간을 다시 할당 받아야하는 문제가 발생한다.

연속적인 자료에 대한 추가,삭제가 빈번하다면 순서 리스트로 표현하는 방법보다는 연결 리스트의 방식을 따르는 것이 부담을 줄일 수 있다.

 

* 단순 연결 리스트

- 단순 연결 리스트는 순서 리스트 운용에서의 문제점을 보완하기 위해 만들어진 구조로 각 원소들을 저장공간의 위치에 상관없이 유연하기 처리하기 위해서 리스트에 포인터를 포함시킨 표현방법이다. 이 방법을 사용할 경우 노드의 추가/삭제 시에도 새로운 노드를 생성하여 삽입하고자 하는 원소의 앞뒤노드와의 연결만 해주면 되기 때문에 순서리스트에서 발생하는 원소들의 이동이 일어나지 않는다.

 

단순 연결 리스트의 구조를 표현하기 위해서는 노드 구조의 정의가 필요

 

* 노드 생성

- 단순 연결 리스트에서의 원소의 삽입/삭제를 위해서는 각 원소를 노드의 구성으로 표현해야한다.

 

연결리스트의 장단점

- 장점 : 노드의 삽입 삭제가 용이하다.

- 연속적으로 기억 공간 없어도 저장이 가능하다.

 

- 단점 : 순서 리스트나 배열보다 기억 공간이 많이 필요하다

- 알고리즘 구현이 복잡하다

- 특정 노드 검색 시 무한 루프에 빠질 수 있다.