[자료구조] 연결리스트의 개념과 배열리스트와의 비교

 

 

 

연결리스트(Linked List)란 ?

포인터를 이용하여 자료를 끊김 없이 연결되어 순차적으로 저장되는 것.

 

배열리스트와의 가장 대표적인 차이점

배열리스트는 물리적 위치가 순차적이지만 ,

연결리스트는 단순히 논리적 위치만 순차적이고
물리적 위치는 순차적이지 않을 수 있다는 것!

 

즉, 최대 원소 개수를 지정하는 것에 대한 차이가 있다.

배열리스트는 무조건 최대 원소 개수를 지정해야하지만 

연결리스트는 지정해줄 필요가 없다.

 

연결리스트의 구조

노드(Node) = 자료 + 링크

 

 

연결리스트의 노드 추가와 제거는
링크 정보를 추가하거나 제거하는 것

배열리스트는 원소의 추가와 제거가
원소의 이동을 의미한다.

---

노드 추가하기

 

 

 

노드 추가시 기존에 연결되어있던 링크를 제거하고
새로운 링크를 추가하여 다시 잇는다

노드 제거하기

 

 

노드 제거 시에도 기존 링크를 제거하고
새로운 링크로 제거한 노드의 앞뒤를 이어준다

---

연결리스트 vs 배열리스트

 

연결리스트의 장점

1. 자료의 추가, 삭제 용이

리스트에 새로운 자료를 추가하거나 제거할때

원소의 이동이 필요하지 않고 링크만 조정하면 되기 때문에

비교적 자료의 수정이 용이하다

 

2. 리스트의 크기 설정 필요 없음 

앞에서 말한것 처럼 링크로 연결되면 되기 때문에

최대 크기를 설정할 필요가 없다는 장점이 있다

 

연결리스트의 단점

1. 구현이 어렵다

포인트를 많이 사용하기때문에 구현이 어렵다

 

2. 탐색연산의 시간이 더 오래 걸린다

원하는 자료의 값을 가져오기 위해서 원하는 위치까지

검색해서 조회해야하기 때문에

같은 갯수의 리스트가 있을때

연결리스트가 배열리스트보다 검색시간이 더 오래 걸린다