JAVA 자료구조 및 알고리즘 [02] : 연결 리스트

연결리스트  노드 : - 자료 구조에 데이터를 담거나 표현하는 기초적인 단위 (ex. 특정 값 혹은 포인터) 연결 리스트의 노드 : - 데이터와 링크 공간 (즉 연결 리스트를 구성하는 작은 단위) - 하나의 노드는 포인터 영역에서 다음 노드를 가리킴 - 노드의 포인터 공간 사용에 따라서 단일, 이중, 원형 등 다양한 연결 리스트 구현 가능 연결 리스트의 특징 : - 크기를 미리 정하지 않고도 동적 할당이 가능 - 삽입과 삭제 연산에서 *오버헤드가 배열보다 적음 - 특정 인덱스로 접근이 불가능하므로 데이터를 검색하려면 순차적으로 첫 노드부터 끝까지 방문해야 함 (따라서 연결 리스트는 삭제 및 삽입이 빈번히 일어나는 환경에서 배열보다 유리함) (연결 리스트에서는 배열과는 달리 데이터가 중간에 삽입되어도 노드 간의 포인터만 수정하면 됨) *오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 및 메모리  - 배열에서 중간에 삽입을 하면 뒤에 데이터들이 뒤로 한 칸씩 밀려나며 오버헤드가 늘어남  - 배열은 데이터를 뒤로 미는 게 아니라 포인터의 연결만 바꿈 삭제 :  - 연결 리스트의 삭제는 삭제할 대상의 포인터를 끊어주거나 노드를 null로 초기화 함.  (가비지 콜렉션이 참조가 끊긴 객체는 추후 메모리를 회수해 감) 검색 : - 배열은 인덱스로 접근하기 때문에 시간복잡도가 O(1),  연결 리스트는 최소 한 번은 노드를 순회해야 하므로 O(n)의 시간복잡도. - 연결 리스트에서 프로그램은 값을 찾을 때까지 노드를 순회 연결 리스트의 종류 : <단일 연결 리스트> - 하나의 포인터 영역을 가지고 다음 노드를 가리키는 연결 리스트 - 항상 첫 노드를 가리키는 head 변수가 존재함  - 각각의 변수는 자신의 다음 노드를 가리킴 - 가리킬 대상이 없으면(ex. 마지막 변수) 포인터 영역은 null을 가리킴 <이중 연결 리스트> - 자신의 앞과 뒤 노드를 가리키기 위해 두 개의 포인터 영역을 가지는 연결 리스트 - 자신과 인접한 모든 노드를 가리킴 (포인터 영역 두 개, 앞 뒤) <원형 연결 리스트> - 마지막 노드가 처음 노드를 가리키는 연결 리스트 - 마지막 노드인 tail 변수가 가장 첫 노드인 head를 가리키며 원의 모습이 됨 - 포인터 영역은 하나임 (원형 단일 연결 리스트)

단일 연결 리스트 구현

이중 연결 리스트 구현

원형 연결 리스트 구현