연결된 목록 구현

연결된 목록은 노드로 알려진 정렬되지 않은 연결 요소 컬렉션을 포함하는 기본이 아닌 데이터 구조입니다.

Linked List는 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조입니다.

연결 리스트는 각 노드가 두 개의 하위 필드를 갖는 노드로 구성됩니다. 필드의 한 부분은 데이터 필드이고 다른 부분은 다음 노드의 주소를 저장하는 링크 필드라고 합니다. 각 링크 필드는 노드를 연결하고 연결 목록.

연결된 목록 개별 블록

구조 노드 {

   int data;
  Node* next; 

}

배열 대신 연결된 목록이 필요한 이유는 무엇입니까?

연결된 목록의 크기는 동적이지만 배열의 경우 크기가 고정되어 있습니다. 컴파일 후에 추가 요소를 추가할 수 없습니다.

배열의 요소 삽입은 배열의 크기에 따라 달라지며 연결 목록에서 요소 삽입은 크기와 무관합니다.

제한 사항
포인터 필드의 각 노드에는 추가 공간이 필요합니다.
임의 액세스가 불가능하며 첫 번째 요소를 제외하고 대상 요소에 액세스하려면 목록을 순회해야 합니다.

Linked list are classified into three types...

• Single linked list : 각 노드에 대해 두 개의 필드를 가지는 리스트의 형태로 하나는 데이터 필드이고 다른 하나는 다음 노드의 주소를 저장하는 링크 필드이다.

• 이중 연결 목록: 각 노드에 세 개의 필드, 즉 이전 노드를 저장하는 필드, 다음 노드에 대한 링크를 저장하는 필드 및 데이터 필드가 있는 양방향 목록.

• 순환 이중 연결 리스트: 순환 양방향 연결 리스트, 순환 이중 리스트는 마지막 노드의 다음 필드에 NULL을 포함하지 않습니다. 마지막 노드의 다음 필드에는 목록의 첫 번째 노드 주소가 포함됩니다.

Linked list consist of head node which stores the link of the first node.

Language used : C++.

기본 구현

목록에 노드 삽입::노드를 추가하려면 노드 생성을 위해 동적으로 메모리를 할당해야 합니다. C++에서는 동적으로 메모리를 할당하기 위해 new 키워드를 사용합니다.

노드를 목록에 추가하려면 헤드 참조와 삽입할 값을 새 노드에 전달해야 합니다.

연결된 목록 개별 블록을 만들기 전에.

CODE

노드 InsertNode(노드 **head,int data ) {

Node *temp=new Node; 
temp->value=data;
temp->next=head;
head=temp;

}

temp라는 노드 변수에 대한 포인터가 생성됩니다.

값을 데이터 필드로 초기화합니다.

링크 필드 부분을 헤드 값(이전 노드의 주소를 포함)으로 초기화합니다.

결국 head는 newnode를 가리킵니다.

따라서 링크가 생성되었습니다.

Linked list 순회: Linked list의 순회는 헤드 노드(첫 번째 노드의 링크를 저장하는 노드)에서 이루어지며, 순회 중 Null을 만나면 Linked list가 끝까지 도달한 것입니다.

CODE

무효 인쇄(노드 *헤드)
{

Node *temp = *head;
cout << "List is   ";
while (temp != NULL)
{
    cout << temp->data << " ";
    temp = temp->next;
}

}

헤드 노드 값을 사용하는 임시 변수입니다.

끝에 도달할 때까지 목록을 순회하는 반복 조건입니다.

목록에서 노드를 발견하는 동안 해당 값을 인쇄합니다.

현재 노드 값을 인쇄한 후 노드의 링크 필드를 가리켜 임시를 업데이트합니다.

NULL을 가리키는 노드에 도달할 때까지 단계를 반복합니다.

따라서 우리는 목록을 순회합니다.

"**head" means pointer to pointer, to modify a pointer reference of the pointer is passed.