연결리스트
•
데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
•
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
•
삽입, 삭제 O(1), 탐색 O(n)
•
다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있음
•
맨 앞에 있는 노드를 헤드라고 함
종류
•
싱글 연결 리스트
◦
다음 노드를 가리키는 next 포인터만 가지는 연결 리스트
◦
이전 요소 접근에 매우 부적합
▪
탐색 시간이 O(n) 1000개의 데이터에 999번째 데이터는 노드를 999번 이동
◦
클래스
class Node {
Node next; // 다음 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
};
Java
복사
•
이중 연결 리스트
◦
next포인터와 이전 노드를 가리키는 prev 포인터도 가지는 연결 리스트
◦
단방향이던 이동 방향을 양방향으로 가능하게 해서 역순 검색이 가능하도록 함
◦
기본적으로 많이 사용되는 방식
▪
실제로 자바의 LinkedList는 이중 연결 리스트로 구현 되어 있음◦
클래스
class Node {
Node next; // 다음 노드 주소를 저장하는 필드
Node prev; // 이전 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
};
Java
복사
•
원형 이중 연결 리스트
◦
첫 번째 노드와 마지막 노드를 각각 연결시켜 원형으로 만든 이중 연결 리스트
◦
티비 채널 순회나 오디오 플레이어 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 곳에서 사용
◦
단일 연결 리스트 원형으로 연결한 ‘원형 싱글 연결 리스트’도 존재함, 하지만 잘 쓰이지 않음
