Introduction - Singly Linked List

Singly linked listdagi har bir node nafaqat qiymatdan, balki reference field(havola maydoni)dan ham iborat. Shuningdek, singly linked list ketma-ketlikdagi nodelardan tashkil topgan.

Bu yerda singly linked listni namunasi:

Singly linked list

Ko'k o'qlar singly linked listdagi nodelarni birgalikda qanday bog'langanini ko'rsatadi.

Node structure

Bu yerda singly linked list nodeining odatiy ta'rifi:

Golang

type SinglyLinkedList struct {
	Value int
	Next  *SinglyLinkedList
}

C++

// Definition for singly-linked list.
struct SinglyListNode {
    int val;
    SinglyListNode *next;
    SinglyListNode(int x) : val(x), next(NULL) {}
};

Java

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

Ko'p hollarda biz butun list uchun head nodedan foydalanamiz.

Operations

Massivdagi farqli ravishda, biz linked listda o'zgarmas vaqtda tasodifiy elementlarga kira olmaymiz. Agar siz i-elementni olishni xohlasangiz, birma-bir bosh tugun(head)dan boshlab o'tib chiqishimiz kerak. Bu uzunligi Nga teng bo'lgan listda index bo'yicha kirishda o'rtacha xollarda O(N) oladi.

Misol uchun, yuqoridagi misolda, head node 23. 3-nodega kirishning birgina yo'li 2-node(6)ga o'tish uchun head nodening next maydonidan foydalanish. Keyin biz 6 qiymatli nodening next maydoni bilan 3-nodega kira olamiz.

Siz index bo'yicha kirishda yomon performancega ega bo'lgan (arrayga bilan solishtirganda) linked list nima uchun foydali ekanligi haqida o'ylayotgan bo'lishingiz mumkin. Keyingi maqolalarda biz insert va delete operatsiyalarini tanishtiramiz va siz linked listning foydalarini tushunib yetasiz.

Shundan so'ng, biz o'zingizning linked listingizni ishlab chiqish uchun mashq taqdim etamiz.

© Leetcode link