자료구조(13) - 단순 연결 리스트

 - 단순 연결 리스트

              : 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조

              : 순서 리스트는 논리적인 순서와  물리적인 순서가 일치함

              : 단순 연결 리스트는 순서 리스트 운영에서의 문제점을 보완하기 위해 만들어진 구조로서

                각 원소들을 저장 공간의 위치에 상과없이 유연하게 처리하기 위해서 리스트에 포인터를 포함시킨

                표현방법을 사용한다.

 

 

 

              : 데이터 부분에는 저장되는 원소가 있고, 링크 부분에는 다음 노드의 위치를 가리키는 포인터 값을 저장한다.

                만약 다음 데이터가 없는 마지막 값일 경우에는 null 값으로 표현된다. 

              : 이런 방식으로 원소가 추가되거나 삭제되었을때 리스트 전체의 순서를 바꿀필요가 없어지게 된다. 

                 -> 원소의 삭제, 삽입에 대해 시간복잡도는 상수 시간인 O(1)이 된다.

              : 또한 노드를 생성할 때 마다, 각 노드의 기억 공간만 할당받으면 되므로,

                리스트에서 사용할 기억공간을 미리 할당받을 필요가 없어 기억 공간의 낭비를 줄일 수 있다.

 

 - 노드 생성

 - 노드 삽입

 - 노드 삭제

 

              : 데이터에는 원소가 저장되고, 링크에는 다음 노드의 주소지값이 저장되고, 마지막 노드일경우에는 링크에                   null 이 저장된다는걸 알면 논리적으로 모든 과정이 설명된다.

 

연결리스트의 장단점

              : 장점

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

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

 

              : 단점

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

                         : 알고리즘 구현이 복잡하다.

                         : 특정 노드 검색 시 무한루프에 빠질 수 있다.  ( 구현 중 같은 주소값을 바라보는 노드가 생성 될 시 )