연결된 목록의 길이를 찾는 방법은 무엇입니까?
연결된 목록이란 무엇입니까?
- 연결된 목록은 데이터 모음을 저장하는 데 사용되는 선형 데이터 구조입니다.
- 연속적인 요소는 포인터로 연결됩니다
- 마지막 요소가 NULL을 가리킴
- 각 요소는 별도의 개체이며 노드라고 합니다.
- 연결된 목록의 각 노드는 두 부분으로 구성됩니다.
- 데이터
- 다음 노드에 대한 참조
연결된 목록의 길이를 찾는 방법은 무엇입니까?
연결 리스트의 길이를 찾는 방법에는 두 가지가 있습니다.
- 반복적 접근 방식
- 재귀 접근법
반복 접근 방식을 사용한 연결 목록의 길이
Linked list 순회를 사용하여 연결 목록의 길이를 찾습니다.
- 헤드는 목록의 첫 번째 노드를 가리킵니다.
- 카운트 변수를 값 0으로 초기화
- Head로 임시 변수 초기화
- 각 노드에 접근할 때마다 count 변수의 값이 1씩 증가합니다.
- null에 도달하면 프로세스를 중지합니다.
- 헤드 참조를 변경하지 마십시오.
자바 코드
package com.journaldev.ds; public class MyLinkedList { public class Node { int data; Node next; } public Node head; public Node tail; public int size; public int getFirst() throws Exception { if (this.size == 0) { throw new Exception("linked list is empty"); } return this.head.data; } public int getLast() throws Exception { if (this.size == 0) { throw new Exception("linked list is empty"); } return this.tail.data; } public void display() { Node temp = this.head; while (temp != null) { System.out.println(temp.data + " "); temp = temp.next; } } public void addFirst(int item) { Node nn = new Node(); nn.data = item; if (this.size == 0) { this.head = nn; this.tail = nn; this.size = this.size + 1; } else { nn.next = this.head; this.head = nn; this.size = this.size + 1; } } public int length() { Node temp = this.head; int count = 0; while (temp != null) { count++; temp = temp.next; } return count; } public static void main(String[] args) { MyLinkedList ll = new MyLinkedList(); ll.addFirst(10); ll.addFirst(20); ll.addFirst(30); ll.addFirst(40); ll.addFirst(50); System.out.println("Length of Linked List is " + ll.length()); } }C 코드
#include <stdio.h> #include <stdlib.h> /* A structure of linked list node */ struct node { int data; struct node *next; } *head; void initialize(){ head = NULL; } /* Inserts a node in front of a singly linked list. */ void insert(int num) { /* Create a new Linked List node */ struct node* newNode = (struct node*) malloc(sizeof(struct node)); newNode->data = num; /* Next pointer of new node will point to head node of linked list */ newNode->next = head; /* make new node as the new head of linked list */ head = newNode; printf("Inserted Element : %d\n", num); } int getLength(struct node *head){ int length =0; while(head != NULL){ head = head->next; length++; } return length; } /* Prints a linked list from head node till the tail node */ void printLinkedList(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } } int main() { initialize(); /* Creating a linked List*/ insert(8); insert(3); insert(2); insert(7); insert(9); printf("\nLinked List\n"); printLinkedList(head); printf("\nLinked List Length : %d", getLength(head)); return 0; }산출
재귀 솔루션을 사용한 연결 목록의 길이
기본 케이스:
- 마지막 노드가 Null 값을 가리킴
- 0 반환
재귀 사례:
- 각 단계에서 현재 노드의 값을 다음 노드로 업데이트
- 콜= 1+재미(curr.next)
예: 연결된 목록에는 3개의 요소(LL1, LL2 및 LL3)가 있습니다. 재귀 호출이 수행될 때 메모리 스택에서 어떤 일이 발생하는지 관찰합니다. 메모리 스택:
메인 함수는 LL1을 호출하고, LL1은 LL2를 호출하고, LL2는 LL3을 호출하고, LL3은 null 값을 호출합니다. Null 값에 도달하면 여기에서 돌아옵니다. 0은 LL3에, LL3은 1을 LL2에, LL2는 2를 LL1에 반환합니다. LL1은 마침내 메인 함수에 3을 반환합니다.
자바 코드
package com.journaldev.ds; public class MyLinkedList { public class Node { int data; Node next; } public Node head; public Node tail; public int size; public int getfirst() throws Exception { if (this.size == 0) { throw new Exception("linked list is empty"); } return this.head.data; } public int RemoveFirst() throws Exception { if (this.size == 0) { throw new Exception("LL is empty"); } Node temp = this.head; if (this.size == 1) { this.head = null; this.tail = null; size = 0; } else { this.head = this.head.next; this.size--; } return temp.data; } public void addFirst(int item) { Node nn = new Node(); nn.data = item; if (this.size == 0) { this.head = nn; this.tail = nn; this.size = this.size + 1; } else { nn.next = this.head; this.head = nn; this.size = this.size + 1; } } public int lengthUsingRecursiveApproach (){ return lengthUsingRecursiveApproach(this.head); } private int lengthUsingRecursiveApproach(Node curr) { // TODO Auto-generated method stub if (curr == null) { return 0; } return 1 + lengthUsingRecursiveApproach (curr.next); } public static void main(String[] args) { MyLinkedList ll = new MyLinkedList(); // insert elements into the Linked List ll.addFirst(10); ll.addFirst(20); ll.addFirst(30); ll.addFirst(40); ll.addFirst(50); // Length of List System.out.println("Recursive Approach length " + ll.lengthUsingRecursiveApproach(ll.head)); } }C 코드
#include <stdio.h> struct Node { int data; struct Node* next; }; void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); (*head_ref) = new_node; } int getCount(struct Node* head) { // Base case if (head == NULL) return 0; return 1 + getCount(head->next); } int main() { struct Node* head = NULL; push(&head, 1); push(&head, 3); push(&head, 1); push(&head, 2); push(&head, 1); printf("count of nodes is %d", getCount(head)); return 0; }산출
시간 복잡도
재귀 및 반복 솔루션 모두에서 O(N)은 길이를 알기 위한 단일 순회입니다.