List (리스트) : 배열처럼 데이터 집합을 보관하는 기능을 하면서 배열과 달리 유연하게 크기를 바꿀 수 있는 자료구조
연결 리스트의 특징
•
Node : 리스트 내의 각 요소
•
Head : 연결 리스트의 첫 번째 노드
•
Tail : 연결 리스트의 마지막 노드
•
Node는 데이터와 다음 노드에 대한 포인터를 가지고 있다.
•
따라서 Node 가 연쇄적으로 연결되어 데이터를 저장하는 자료구조를 말한다.
연결 리스트 장단점
장점
•
미리 자료구조의 크기를 지정할 필요가 없다.
•
새로운 노드의 추가, 삽입, 삭제가 쉽고 빠르다. (배열과 비교하여)
•
다음 노드를 얻어오는 연산에 대해 비용이 발생하지 않는다.
단점
•
Node 내에 다음 노드를 가리키는 포인터 때문에 각 노드마다 4byte 메모리가 추가로 필요하다.
•
특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도가 느리다.
◦
노드의 개수가 n 이라면 최악의 경우 n회의 노드 탐색 루프를 실행해야 특정 위치에 있는 노드를 찾을 수 있다.
