Вивчайте Implementing Singly Linked Lists

Свайпніть щоб показати меню

A singly linked list is a linear data structure where each element, called a node, contains two parts: a value and a reference to the next node in the sequence. Unlike arrays, singly linked lists do not store elements in contiguous memory locations. Instead, each node points to the next, forming a chain that continues until the last node, which points to nil (no further node).

Key properties of singly linked lists include:

Each node holds a single value and a pointer to the next node;
The list has a single entry point, called the head;
Traversal is one-way, from the head toward the end;
Insertion and deletion operations can be performed efficiently at the beginning of the list.

Singly linked lists are useful when you need to manage a collection of items with frequent insertions or deletions, especially at the front of the list. They are commonly used in scenarios such as implementing queues, stacks, and other dynamic data structures where flexible memory management is important.

main.go


              12345678910111213141516171819202122232425262728
            
package main

import "fmt"

// Node represents a single element in a singly linked list
type Node struct {
    Value int
    Next  *Node
}

func main() {
    // Create three nodes
    node1 := &Node{Value: 10}
    node2 := &Node{Value: 20}
    node3 := &Node{Value: 30}

    // Link the nodes together
    node1.Next = node2
    node2.Next = node3

    // Print the list
    current := node1
    for current != nil {
        fmt.Printf("%d ", current.Value)
        current = current.Next
    }
    fmt.Println()
}

Adding Elements to a Singly Linked List

A singly linked list is a collection of nodes, where each node holds data and a reference (pointer) to the next node in the sequence. Adding elements to a singly linked list is a fundamental operation, and you will often need to insert elements either at the beginning or at the end of the list.

Adding at the Beginning

To add a new element at the beginning:

Create a new node containing the value you want to add;
Set the new node's next pointer to the current head of the list;
Update the head of the list to point to the new node.

This operation is efficient because you do not need to traverse the list; it always takes constant time, O(1).

Conceptual Example:

Suppose you have a list: 1 -> 2 -> 3 and you add 0 at the beginning. The steps are:

Create a node with value 0.
Set 0's next to the current head (1).
Update the head to the new node (0).

The list becomes: 0 -> 1 -> 2 -> 3.

Adding at the End

To add a new element at the end:

Create a new node containing the value you want to add;
If the list is empty, set the head to the new node;
Otherwise, start at the head and traverse the list to find the last node (where next is nil);
Set the last node's next pointer to the new node.

This operation requires visiting each node, so it takes linear time, O(n), where n is the number of nodes in the list.

Conceptual Example:

Suppose you have a list: 1 -> 2 -> 3 and you add 4 at the end. The steps are:

Create a node with value 4.
Traverse from 1 to 3 (the last node).
Set 3's next to the new node (4).

The list becomes: 1 -> 2 -> 3 -> 4.

Adding elements at the beginning is usually faster than adding at the end, unless you maintain a pointer to the last node (tail) of the list.

main.go


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
            
package main

import (
	"fmt"
)

// Node represents a single node in the singly linked list
 type Node struct {
	data int
	next *Node
}

// LinkedList represents the singly linked list
 type LinkedList struct {
	head *Node
}

// AddAtHead adds a new node at the beginning of the list
func (l *LinkedList) AddAtHead(data int) {
	newNode := &Node{data: data}
	newNode.next = l.head
	l.head = newNode
}

// AddAtTail adds a new node at the end of the list
func (l *LinkedList) AddAtTail(data int) {
	newNode := &Node{data: data}
	if l.head == nil {
		l.head = newNode
		return
	}
	current := l.head
	for current.next != nil {
		current = current.next
	}
	current.next = newNode
}

// Print displays the elements of the list
func (l *LinkedList) Print() {
	current := l.head
	for current != nil {
		fmt.Printf("%d ", current.data)
		current = current.next
	}
	fmt.Println()
}

func main() {
	list := &LinkedList{}

	list.AddAtHead(3)
	list.AddAtHead(1)
	list.AddAtTail(5)
	list.AddAtTail(7)
	list.AddAtHead(0)

	fmt.Print("Linked list: ")
	list.Print()
}

Removing Elements from a Singly Linked List

You will often need to remove elements from a singly linked list. There are two common scenarios:

Removing the first node (head);
Searching for and removing a node by its value.

Removing the Head Node

To remove the head node:

Update the head pointer to the next node;
The removed node will be automatically garbage collected if there are no other references.

This operation takes constant time, O(1), because you do not need to traverse the list.

Example:

If your list is 1 -> 2 -> 3 and you remove the head, the new list will be 2 -> 3.

Removing a Node by Value

To remove a node by its value:

Start at the head and traverse the list;
Keep track of the previous node as you move forward;
If you find a node with the target value:
- If it is the head, update the head pointer as above;
- Otherwise, set the next pointer of the previous node to skip the current node and point to the next node instead;
If the value is not found, the list remains unchanged.

Important: Always check for an empty list and handle the case where the node to remove is at the head.

Example:

Given the list 1 -> 2 -> 3:

Removing the node with value 2 results in 1 -> 3.
Removing the node with value 1 (the head) results in 2 -> 3.

These removal patterns ensure your singly linked list stays properly connected after an element is deleted.

main.go


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
            
package main

import (
	"fmt"
)

type Node struct {
	value int
	next  *Node
}

type SinglyLinkedList struct {
	head *Node
}

// Add a new node at the end of the list
func (list *SinglyLinkedList) Append(value int) {
	newNode := &Node{value: value}
	if list.head == nil {
		list.head = newNode
		return
	}
	current := list.head
	for current.next != nil {
		current = current.next
	}
	current.next = newNode
}

// Remove the head node
func (list *SinglyLinkedList) RemoveHead() {
	if list.head == nil {
		return
	}
	list.head = list.head.next
}

// Remove the first node with the given value
func (list *SinglyLinkedList) RemoveByValue(value int) {
	if list.head == nil {
		return
	}
	// If the head needs to be removed
	if list.head.value == value {
		list.head = list.head.next
		return
	}
	prev := list.head
	current := list.head.next
	for current != nil {
		if current.value == value {
			prev.next = current.next
			return
		}
		prev = current
		current = current.next
	}
}

// Print all values in the list
func (list *SinglyLinkedList) Print() {
	current := list.head
	for current != nil {
		fmt.Printf("%d ", current.value)
		current = current.next
	}
	fmt.Println()
}

func main() {
	list := &SinglyLinkedList{}
	list.Append(10)
	list.Append(20)
	list.Append(30)
	list.Append(40)
	fmt.Print("Original list: ")
	list.Print()

	list.RemoveHead()
	fmt.Print("After removing head: ")
	list.Print()

	list.RemoveByValue(30)
	fmt.Print("After removing value 30: ")
	list.Print()
}

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 1. Розділ 4

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Секція 1. Розділ 4