배열
배열을 다른 이름으로 선형리스트라고 부른다.
연속적인 메모리에 저장하는 리스트, 순차 자료구조이다.
배열을 이용하여 스택, 큐, 데크를 구현할 수 있다.
배열의 특징
가장 간단하다.
접근 속도가 빠르다.
자료를 보관할 때 (n+1)/2개의 자료를 이동해야 한다.
자료를 삭제할 때 (n-1)/2개의 자료를 이동해야 한다.
자료를 보관하기 위한 메모리 외에 다른 메모리를 할당하지 않아 메모리 효율이 1이다.
연결리스트
노드들의 선형 집합, 순차 자료구조가 아니다.
노드는 자료와 링크로 구성
링크는 다른 노드의 위치 정보
연결리스트의 특징
배열에 비해 삽입, 삭제 연산이 간단하다.
자료를 보관하는 메모리 외에 링크 부분이 필요하므로 메모리 효율이 배열보다 떨어진다.
링크가 중간에 끊어지면 다음 노드를 찾는 것이 어렵다.
희소 행렬일 때는 연결 리스트로 표현하는 것이 기억 장소를 절약할 수 있다.
링크의 개수에 따라 단순 연결 리스트와 이중 연결 리스트로 구분할 수 있다.
마지막 노드의 링크가 맨 앞의 노드를 가리키는 형태를 환형(Circular) 연결 리스트라 부른다.