[자료구조] 연속 리스트(Contiguous List) 와 연결 리스트(Linked List)

연속 리스트(Contiguous List) 

 

배열처럼 연속적인 기억 장소에 데이터가 저장되는 자료구조. 

연속적으로 데이터가 저장되어있어 검색에는 용이하지만, 데이터의 삽입이나 삭제에 단점이있다. 삽입과 삭제가 일어나는 경우 자료의 이동이 필요하다는 번거로움이 있다.

 

 

연결 리스트(Linked List)

데이터를 임의기억공간에 기억시키되, 데이터 항목의 순서에에 따라 노드의 포인터를 이용하여 서로 연결시킨 자료구조. 

새로운 데이터를 추가하고 삭제하는 것이 용이하고 효율적이다.

배열처럼 메모리에 연속적으로 위치하지 않고 구조의 재구성이 필요없다. 메모리를 더 효율적으로 사용할 수 있기 때문에 

대용량의 데이터 처리에 적합하다. 하지만 연결이 끊어지면 다음 노드를 찾기가 어렵고 속도가 느리다는 단점이 있다. 

 

연결리스트 구분

연결방향에 따라 단일 연결 리스트, 연결리스트, 이중연결리스트, 환형 연결리스트가 있다. 

단일 연결 리스트

각 노드에 자료공간과 한개의 포인터 공간이 있고 각 노드의 포잍너는 다음 노드를 가리킨다.

 

이중연결리스트

단일 연결리스트와 비슷하지만 포인터 공간이 두개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 

 

원형 연결리스트

일반적인 연결리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조