Singly linked list என்றால் என்ன மற்றும் எப்போது இதைப் பயன்படுத்துவீர்கள்?

Question

Accepted Answer

**Singly linked list** என்பது **nodes** களின் ஒரு சங்கிலி, இதில் ஒவ்வொரு node ஒரு மதிப்பு மற்றும் **next** node க்கு ஒரு pointer வைத்திருக்கும். Array போல் இல்லாமல், nodes ஒருங்கமாக இல்லை — அவை memory இல் எங்கும் இருக்கலாம், references மூலம் இணைக்கப்பட்டிருக்கும்.

## கட்டமைப்பு

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## எடுத்துக்காட்டு

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## சிக்கலான தன்மை

| செயல்பாடு | நேரம் |
|---|---|
| Head இல் சேர்க்க/நீக்க | O(1) |
| Index மூலம் அணுக | O(n) |
| தேடல் | O(n) |

## பரிமாற

- **வலிமை:** O(1) முன்பக்கத்தில் சேர்க்க/நீக்க; மறு-할당 இல்லாமல் வளரும்; வீணான திறன் இல்லை.
- **பலவீனம்:** தற்கால அணுகல் இல்லை; ஒவ்வொரு node pointer overhead ஐ கொண்டிருக்கும்; மோசமான cache locality (சிதறிய memory).

## இது ஏன் முக்கியமானது

Linked lists முடிகளில் அடிக்கடி சேர்க்கும் அல்லது நீக்கும் போது மற்றும் நடுவில் குறிப்பிட்ட index க்கு அரிதாக செல்லும் போது — எடுத்துக்காட்டாக, stacks, queues, மற்றும் adjacency lists ஆகியவற்றின் அடிப்படையாக பயன்படுகிறது.

இங்கு pointer manipulation ஐ புரிந்துகொள்வது trees, graphs, மற்றும் பல interview பிரச்சனைகளுக்கான அடிப்படையாகும்.

செயல்பாடு	நேரம்
Head இல் சேர்க்க/நீக்க	O(1)
Index மூலம் அணுக	O(n)
தேடல்	O(n)