1. 리스트 순서를 가진 데이터의 집합을 가리키는 추상자료형. 값의 중복을 허용한다. 순차 리스트 : 배열을 기반으로 구현. : Random access 가능. : 삽입/삭제 연산에 불리. 연결 리스트 : 메모리의 동적할당을 기반으로 구현. : 삽입/삭제에 유리. : 탐색에 불리. 2. 연결 리스트 자료의 논리적인 순서와 물리적인 순서가 일치하지 않을 수 있다. 개별적인 노드를 연결하여 하나의 자료구조를 형성. class Node { T data'; Node link; } node 데이터 필드 링크 필드 : 연결된 노드의 참조값을 저장. head 첫번째 노드에 대한 참조값을 가지고 있음. tail 마지막 노드에 대한 참조값을 가지고 있음. 가. 단순 연결 리스트 다음 노드에 대한 참조값만 가지고 있음. ..

1. 연결 리스트 요소가 인접한 메모리 위치에 저장되지 않는 선형 데이터 구조다. 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조다. //sigle list의 node class Node { public: int data; Node* next; Node(){ data = 0; next = NULL; } Node(int data){ this->data = data; this->next = NULL; } }; 인접한 메모리 위치에 저장되지 않아서 공간 효율성이 높지만 반대로 인접한 메모리 위치에 저장되지 않기 때문에 순차적 접근이 강제된다. 이에 검색에 있어서 O(n)만큼의 시간이 소요된다. 연결리스트는 싱글연결리스트, 이중연결리스트, 원형싱글연결리스트 그리고 원형이중연결리스트..