순차 자료구조의 문제점
- 연산 시간의 문제: 삽입 삭제 후에 연속적으로 원소들을 이동시키는 작업이 필요한데, 삽입 삭제하는 양이나 애당초 배열의 크기가 클수록 연산량이 많아져 성능의 문제가 발생한다.
- 저장공간의 문제: 배열 자체의 메모리 비효율성 문제로 동적으로 변해야 하는 경우 낭비가 발생한다.
앞서 이유로 인해 대안으로 연결 자료구조 방식이 있다. 다만 순차 자료구조가 문제의 특성에 따라서는 연산에서나 저장공간에서나 이득일 수도 있다.
연결(linked) 자료구조 방식
논리적 순서와 물리적 순서가 일치하지 않는 자료구조 방식이다. 원소들 저장할 때 다음 원소의 주소도 함께 저장해놓는다. 크기 변경이 유연하고, 원소를 삽입/삭제할 때마다 원소를 이동시킬 필요가 없다.
연결 방식에 따른 리스트 구분
단순 연결 리스트
노드(Node)란? 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조. <원소, 다음 노드 주소>로 구성되어 있다.
data field는 원소의 값을 저장하며 원소의 형태에 따라 하나의 이상의 필드로 구성된다.
link field는 다음 노드의 주소값을 저장한다. 리스트의 마지막은 null값이다.
리스트를 따라가려면 첫번째 노드 주소를 담은 노드 변수가 필요하다.
노드에 링크 필드가 하나인 리스트이다.
- 노드 삽입
- 노드 삭제
원형 연결 리스트 circular linked list
단순 연결 리스트의 마지막 노드가 첫번째 노드를 가리키게 한 것. 첫번째와 마지막 노드 둘 다 빠르게 접근할 수 있다.
이중 연결 리스트 doubly linked list
양쪽을 순회할 수 있도록 만들어진 리스트. 구조는 다음과 같다.
728x90
반응형