[Data Structure] 연결 리스트

연결 리스트란

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 저장하는 자료구조이다.

데이터를 담고 있는 노드들이 연결되어 있는데 노드의 포인터가 다음이나 이전의 노드와 연결된다.

 

단일 연결리스트, 이중 연결 리스트 등이 있다.

 

연결 리스트의 특징

• 빈틈없는 데이터의 적재
• 불연속적으로 메모리 공간을 차지
• 포인터를 통합 전급

 

연결 리스트의 장단점

장점

연결리스트는 동적 크기를 가진다. 따라서 메모리 크기가 충분하다면 필요한만큼 데이터를 삽입, 삭제할 수 있다.

따라서 연결리스트는 삽입, 삭제가 용이하다.

 

메모리 공간을 불연속적으로 차지하기 때문에 메모리 관리가 편리하다. 배열의 경우 연속적인 메모리 공간이 필요하지만 연결리스트는 그렇지 않다.

단점

임의로 인덱스에 접근할 수 없다. 0번 째 인덱스부터 순차적으로 접근해야하기 때문에 검색에는 비효율적이다.

포인터를 위한 메모리 공간이 별도로 필요하다.