•
정의
◦
배열의 추가/삭제 연산에 대한 비효율성을 극복하고자 등장한 자료구조다.
◦
각 요소는 다음 노드 연결에 대한 정보를 담은 포인터와 함께 저장된다.
◦
단일 리스트, 이중 연결 리스트, 원형 연결 리스트 등의 종류가 존재한다.
•
특징
◦
새로운 요소가 추가될 때마다 동적으로 메모리를 할당한다.
◦
Sequential Access를 지원한다.
◦
인덱스나 위치와 같은 물리적 배치를 사용하지 않고 참조 시스템을 사용한다.
•
시간복잡도
조회 | 검색 | 삽입 | 제거 |
O(n) | O(n) | O(1) | O(1) |
•
이런 이유로 각 연산에 대한 시간복잡도가 다르다.
◦
조회의 경우 Array는 O(1), List는 O(n)
◦
삽입/삭제의 경우 Array는 O(n), List는 O(1)의 시간복잡도
•
따라서 얼마만큼의 데이터를 저장할지 미리 알고 있고 조희를 많이한다면 Array를 몇개의 데이터를 저장할지 불확실하고 삽입/삭제가 잦다면 Linked list를 사용하자.
