Как найти длину связанного списка?
Что такое связанный список?
- Связанный список – это линейная структура данных, используемая для хранения коллекций данных.
- Последовательные элементы связаны указателями
- Последний элемент указывает на NULL
- Каждый элемент представляет собой отдельный объект и называется узлом.
- Каждый узел в связанном списке состоит из двух частей.
- Данные
- Ссылка на следующий узел
Как найти длину связанного списка?
Есть два способа найти длину связанного списка:
- Итеративный подход
- Рекурсивный подход
Длина связанного списка с использованием итеративного подхода
Мы будем использовать обход связанного списка, чтобы найти длину связанного списка.
- Начало указывает на первый узел списка.
- Инициализировать переменную count со значением 0
- Инициализируйте переменную temp с помощью Head
- При доступе к каждому узлу значение переменной count увеличивается на 1.
- Остановить процесс, когда мы достигнем нуля.
- Не меняйте ссылку на заголовок.
Код на Java
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()); } }Код на С
#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; }Выход
Длина связанного списка с использованием рекурсивного решения
Базовый вариант:
- Последний узел указывает на нулевое значение
- Вернуть 0
Рекурсивный случай:
- На каждом шаге обновляйте значение текущего узла до следующего узла.
- Позвонить=1+fun(curr.next)
Пример: в связанном списке 3 элемента: LL1, LL2 и LL3. Мы будем наблюдать, что происходит в стеке памяти при выполнении рекурсивного вызова. СТЕК ПАМЯТИ:
Основная функция вызывает LL1, LL1 вызывает LL2, LL2 вызывает LL3, LL3 вызывает нулевое значение. По достижении нулевого значения мы возвращаемся отсюда. 0 возвращается в LL3, LL3 возвращает 1 в LL2, LL2 возвращает 2 в LL1. Наконец, LL1 возвращает 3 основной функции.
Код на Java
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)); } }Код на С
#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) как в рекурсивном, так и в итеративном решении, поскольку все, что нам нужно, — это один обход, чтобы узнать длину.