如何查找链接列表的长度？
时间：2020-02-23 14:33:08 来源:igfitidea点击:
什么是链表？
- 链表是一种线性数据结构，用于存储数据集合
- 连续元素通过指针连接
- 最后一个元素指向NULL
- 每个元素都是一个单独的对象，称为节点
- 链表中的每个节点由两部分组成
- 参考下一个节点
如何查找链接列表的长度？
有两种方法可以找到链表的长度：
- 迭代法
- 递归方法
使用迭代方法的链表长度
我们将使用"链表"遍历来查找链表的长度。
头指向列表的第一个节点。
初始化计数变量，值为0
用Head初始化temp变量
当我们访问每个节点时，count变量的值增加1。
当我们达到空值时，停止该过程。
不要更改头部参考。
LinkedList长度的迭代方法
Java代码
package com.theitroad.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;
}
使用递归解的链表长度
基本情况：
- 最后一个节点指向空值
- 返回0
递归案例：
- 在每个步骤中，将当前节点的值更新到下一个节点
- 通话= 1+趣味(curr.next)
递归解
示例：链接列表中有3个元素：LL1，LL2和LL3。
当进行递归调用时，我们将观察内存堆栈中会发生什么。
内存堆栈：
记忆体堆叠
主函数调用LL1，LL1调用LL2，LL2调用LL3，LL3调用空值。
当达到Null值时，我们从这里返回。
LL3返回0，LL3返回1到LL2，LL2返回2到LL1。
LL1最后将3返回到主函数。
Java代码
package com.theitroad.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;
}
