リンクリストの長さを見つける方法はありますか？
リンクリストとは何ですか？ (Linkurisuto to wa nan desu ka?)
- A linked list is a linear data structure used for storing collections of data
- Successive elements are connected by pointers
- The last element points to NULL
- Each element is a separate object and is called a Node
- Each node in a linked list comprises of two partsData
Reference to Next Node
リンクリストの長さを見つける方法は？
連結リストの長さを見つける方法は2つあります。
-
- 反復的なアプローチ
- 再帰的なアプローチ
イテレーターアプローチを使用してリンクリストの長さを求める。
私たちは連結リストのトラバーサルを使用して、連結リストの長さを見つけます。
- Head Points to the First Node of The List.
- Initialize the count variable with value 0
- Initialize the temp variable with Head
- As we access each Node, the value of count variable is increased by 1.
- Stop The process when we reach null.
- Do not change the head reference.
Javaでのコード
package com.scdev.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;
}
出力
再帰的な解法を使って、リンクリストの長さを求める方法
ベースケース：
- Last Node points to Null value
- Return 0
再帰的な場合：
- At each step update the Value of Current Node to the Next Node
- Call= 1+fun(curr.next)
リンクリストにはLL1、LL2、LL3の3つの要素があります。再帰呼び出しが行われる際にメモリスタックで何が起こるかを観察します。メモリスタック：
主な機能はLL1を呼び出し、LL1はLL2を呼び出し、LL2はLL3を呼び出し、LL3はnull値を呼び出します。null値に到達したため、ここから戻ります。0はLL3に返され、LL3は1をLL2に返し、LL2は2をLL1に返します。LL1は最終的に3を主な機能に返します。
Javaでのコード
package com.scdev.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)です。長さを知るために必要なのは、単一のトラバースだけです。
