데이터 구조 및 알고리즘-연결된 목록
연결 목록은 연결을 통해 함께 연결되는 일련의 데이터 구조입니다.
연결된 목록은 항목을 포함하는 일련의 링크입니다. 각 링크에는 다른 링크에 대한 연결이 포함되어 있습니다. 연결된 목록은 배열 다음으로 두 번째로 많이 사용되는 데이터 구조입니다. 다음은 Linked List의 개념을 이해하는 데 중요한 용어입니다.
Link − 링크드리스트의 각 링크는 요소라는 데이터를 저장할 수 있습니다.
Next − 링크 된 목록의 각 링크는 다음이라는 다음 링크에 대한 링크를 포함합니다.
LinkedList − 연결된 목록에는 First라는 첫 번째 링크에 대한 연결 링크가 포함되어 있습니다.
링크 된 목록 표현
연결된 목록은 모든 노드가 다음 노드를 가리키는 노드 체인으로 시각화 할 수 있습니다.
위의 그림에 따라 고려해야 할 중요한 사항은 다음과 같습니다.
Linked List에는 first라는 링크 요소가 있습니다.
각 링크에는 데이터 필드와 next라는 링크 필드가 있습니다.
각 링크는 다음 링크를 사용하여 다음 링크와 연결됩니다.
마지막 링크는 링크를 null로 전달하여 목록의 끝을 표시합니다.
연결된 목록의 유형
다음은 다양한 유형의 연결 목록입니다.
Simple Linked List − 항목 탐색은 앞으로 만 가능합니다.
Doubly Linked List − 항목을 앞뒤로 탐색 할 수 있습니다.
Circular Linked List − 마지막 항목은 다음으로 첫 번째 요소의 링크를 포함하고 첫 번째 요소는 이전으로 마지막 요소에 대한 링크를 포함합니다.
기본 작동
다음은 목록에서 지원하는 기본 작업입니다.
Insertion − 목록 시작 부분에 요소를 추가합니다.
Deletion − 목록의 시작 부분에있는 요소를 삭제합니다.
Display − 전체 목록을 표시합니다.
Search − 주어진 키를 사용하여 요소를 검색합니다.
Delete − 주어진 키를 사용하여 요소를 삭제합니다.
삽입 작업
연결 목록에 새 노드를 추가하는 것은 두 단계 이상의 활동입니다. 여기에서 다이어그램을 통해이를 학습 할 것입니다. 먼저 동일한 구조를 사용하여 노드를 만들고 삽입해야하는 위치를 찾습니다.
노드를 삽입한다고 상상해보십시오. B (NewNode), 사이 A (LeftNode) 및 C(RightNode). 그런 다음 C 옆에있는 B.-
NewNode.next −> RightNode;다음과 같이 보일 것입니다.
이제 왼쪽의 다음 노드가 새 노드를 가리켜 야합니다.
LeftNode.next −> NewNode;
그러면 두 노드의 중간에 새 노드가 배치됩니다. 새 목록은 다음과 같아야합니다.
노드가 목록의 시작 부분에 삽입되는 경우 유사한 단계를 수행해야합니다. 끝에 삽입하는 동안 목록의 두 번째 마지막 노드는 새 노드를 가리켜 야하고 새 노드는 NULL을 가리 킵니다.
삭제 작업
삭제는 또한 한 단계 이상의 프로세스입니다. 그림 표현으로 배웁니다. 먼저 검색 알고리즘을 사용하여 제거 할 대상 노드를 찾습니다.
이제 대상 노드의 왼쪽 (이전) 노드가 대상 노드의 다음 노드를 가리켜 야합니다.
LeftNode.next −> TargetNode.next;
그러면 대상 노드를 가리키는 링크가 제거됩니다. 이제 다음 코드를 사용하여 대상 노드가 가리키는 것을 제거합니다.
TargetNode.next −> NULL;
삭제 된 노드를 사용해야합니다. 메모리에 보관할 수 있습니다. 그렇지 않으면 메모리 할당을 해제하고 대상 노드를 완전히 지울 수 있습니다.
역 동작
이 작업은 철저한 작업입니다. 헤드 노드가 마지막 노드를 가리 키도록 만들고 전체 연결 목록을 반대로 만들어야합니다.
먼저 목록 끝으로 이동합니다. NULL을 가리켜 야합니다. 이제 이전 노드를 가리 키도록합니다.
마지막 노드가 마지막 노드가 아닌지 확인해야합니다. 따라서 마지막 노드를 가리키는 헤드 노드처럼 보이는 임시 노드가 있습니다. 이제 모든 왼쪽 노드가 이전 노드를 하나씩 가리 키도록합니다.
헤드 노드가 가리키는 노드 (첫 번째 노드)를 제외하고 모든 노드는 이전 노드를 가리켜 새로운 후속 노드가되어야합니다. 첫 번째 노드는 NULL을 가리 킵니다.
임시 노드를 사용하여 헤드 노드가 새로운 첫 번째 노드를 가리 키도록 할 것입니다.
이제 연결 목록이 반전됩니다. C 프로그래밍 언어로 연결된 목록 구현을 보려면 여기 를 클릭하십시오 .