배열과 연결리스트 Array, Linked List

 

배열

 

가장 간단한 구조로, 각 요소들은 인덱스 값을 같이 표현한다.

배열을 이루는 각 자료들을 배열 요소라 하고, 배열된 순서대로 위치를 저장한다.

기록 밀도가 1이지만 삽입가 삭제가 어렵고 종속적인 것이 단점이다.

 

 

찾고자 하는 인덱스를 찾기 위해서는 인덱스 번호만 알면 되기에 바로 찾을 수 있지만,

데이터를 삭제하거나 삽입 할땐 그 뒤의 요소들이 모두 시프트 되기 때문에 오래걸린다.

 

 

연결 리스트

 

자료를 구성할 때 포인터를 포함해서 자료를 구성하는 형태로

포인터를 이용하여 다음 자료를 찾는다.

 

노드의 삽입과 삭제를 할때 변경하고 포인터 위치만 바꾸어 주기 때문에 속도가 빠르지만, 

정보를 검색할때 포인터를 여러번 타고 들어가야 하기 때문에 느려진다.

 

 

단일 연결 리스트

 

단일 연결 리스트는 노드마다 1개의 링크를 가지고 있으며 마지막은 null이다.

뒤의 노드는 검색하기 편하지만 전 노드로 돌아가려면 처음부터 검색해야한다는 단점이 있다

 

 

단일 원형 연결리스트

 

 

가장 마지막 노드의 링크가 리스트의 처음 노드를 가리키도록 하는 연결리스트이다.

 

 

이중 연결 리스트

 

한 노드에서 후속 노드 및 선행 노드를 모두 가리키는 포인터를 갖는다.

후속 노드 및 선행 노드로 빈번하게 이동할 경우 사용되며, 마지막 포인터는 null을 가리킨다.