[알고리즘] 리스트 - 선형, 단일 연결, 이중 연결, 원형 연결

리스트

동일한 값이 두 번 이상 나타날 수 있는 셀 수 있는 정렬된 값을 나타내는 자료의 구조

시퀀스(Sequence)라고도 함

 

종류

• 선형
• 단일 연결
• 이중 연결
• 원형 연결

선형:

순서를 가지고 있다

순차 방식으로 구현

원소를 논리적인 순서대로 연속하여 저장

 

원소 삽입

1. 삽입할 빈 자리 만들기
2. 빈 자리 이후의 원소를 한자리씩 뒤로 이동
3. 빈 자리에 원소 삽입

 

원소 삭제

1. 삭제한 자리 이후의 원소들을 한 자리씩 앞으로 이동

단점

• 삽입, 삭제가 비효율적
• 그래서 개선한 방법이 단일 연결 리스트

 

단일 연결: 

저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함

각 노드는 다음 노드를 가리키는 포인터(주소 값)를 가짐

맨 앞부분은 머리(Head), 끝 부분은 꼬리(Tail)

 

노드 추가

1. 앞 노드가 새 노드를 가르키고
2. 새 노드가 앞의 원래 있던 노드를 가르킨다.

 

노드 삭제

1. 이전 노드가 삭제한 노드가 가리키던 노드를 가리키게 한다.

 

단점

• 포인터 데이터가 사라지면, 뒤의 모든 데이터 손실
• 그래서 개선한게 이중연결

 

이중 연결

다음 노드뿐만 아니라 이전 노드의 참조도 같이 가리키게 한다.

[이전 노드 가르키는 포인터][데이터][다음 노드 가르키는 포인터]

 

노드 삽입과 삭제 방법은 단일 연결 노드와 비슷하다

 

원형 연결

이중 연결 리스트에서 마지막 원소가 널(Null) 대신 처음 원소를 가리키게 하면 원형 연결 리스트가 된다.