Go Beyond Basics: Exploring the Practical Side of Linked Lists in Go Programming
A linked list is a data structure consisting of a sequence of elements where each element points to the next element. The elements in a linked list are called “nodes.”
A node typically has two parts:
- Data: This is the actual piece of information you want to store.
- Next: a reference to the next node
A node only knows about what data it contains, and who its neighbor is.
A linked list doesn’t need a contiguous memory block as an Array.
Feel free to consult this exceptional article for a nuanced and articulate elucidation of the theory behind Linked Lists.
https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d
Let’s dive into a practical aspect of the Linked List. Learn Linked List by Building Music Playlist.
In a music playlist, each song can be represented as a node in a linked list. Each node contains information about the song (e.g., title, artist, duration) and a reference to the next song in the playlist. The last song’s reference is set to nil to indicate the end of the playlist.
package main
import "fmt"
// Song represents a song in the playlist.
type Song struct {
Title string
Artist string
Duration int // in seconds
Next *Song
}
// Playlist represents a linked list of songs.
type Playlist struct {
Head *Song
}
// AddSong adds a new song to the end of the playlist.
func (pl *Playlist) AddSong(title, artist string, duration int) {
newSong := &Song{
Title: title,
Artist: artist,
Duration: duration,
Next: nil,
}
if pl.Head == nil {
pl.Head = newSong
return
}
last := pl.Head
for last.Next != nil {
last = last.Next
}
last.Next = newSong
}
// DisplayPlaylist prints the songs in the playlist.
func (pl *Playlist) DisplayPlaylist() {
current := pl.Head
for current != nil {
fmt.Printf("Title: %s, Artist: %s, Duration: %d seconds\n", current.Title, current.Artist, current.Duration)
current = current.Next
}
}
func main() {
// Create a playlist
playlist := Playlist{}
// Add songs to the playlist
playlist.AddSong("Song 1", "Artist A", 180)
playlist.AddSong("Song 2", "Artist B", 240)
playlist.AddSong("Song 3", "Artist C", 200)
// Display the playlist
fmt.Println("Playlist:")
playlist.DisplayPlaylist()
}Let’s explain two methods of the program
1. AddSong()
func (pl *Playlist) AddSong(title, artist string, duration int) {
newSong := &Song{
Title: title,
Artist: artist,
Duration: duration,
Next: nil,
}
if pl.Head == nil {
pl.Head = newSong
return
}
last := pl.Head
for last.Next != nil {
last = last.Next
}
last.Next = newSong
}The AddSong method is designed to add a new song to the linked list represented by the Playlist struct.
Steps Involved:
i. Create a new Song: It will create a new song by initializing a Song struct and setting Next to nil .
ii. Check if a playlist is empty: If the pl.Head is nil it means the list is empty. If the list is empty then the new song becomes the head of the playlist and the function returns.
iii. Find the last node in the playlist: last := pl.Head initialize a pointer last to the Head of the list. It iterates the list until it finds the last node where Next = nil . Inside the loop, it moves the pointer last = last.Next to the next node in the list.
iv. Add the new song to the playlist: last.Next = newSong adds the new song to the end of the list by updating the Next field of the last node to point to the new song. This way, the new song becomes the last node in the list.
2. DisplayPlayList()
func (pl *Playlist) DisplayPlaylist() {
current := pl.Head
for current != nil {
fmt.Printf("Title: %s, Artist: %s, Duration: %d seconds\n", current.Title, current.Artist, current.Duration)
current = current.Next
}
}Steps Involved:
i. Initialize Current Pointer: initializes a pointer current to the Head of the list. This pointer is used to traverse through the list.
ii. Traverse and Display: initiates a loop that continues until the end of the list is reached (i.e., current becomes nil).
iii. Move to the Next Node: moves the current pointer to the next node in the list, allowing the loop to continue to the next song.
Let’s add a few features to this playlist:
3. Get the Length of the Playlist
func (pl *Playlist) Length() int {
count := 0
current := pl.Head
for current != nil {
count++
current = current.Next
}
return count
}i. Initialize Count and Current Pointer:
Initialize a counter to keep track of the number of songs.
Initializes a pointer current to the Head of the list. This pointer is used to traverse through the list.
ii. Count Nodes:
Initiates a loop that continues until the end of the list is reached (i.e., current becomes nil).
Inside the loop, count++ increments the counter for each node (song) encountered in the list.
iii. Move to the Next Node:
moves the current pointer to the next node in the list, allowing the loop to continue counting.
iv. Return the Count
4. Search for a Song
func (pl *Playlist) FindSong(title string) *Song {
current := pl.Head
for current != nil {
if current.Title == title {
return current
}
current = current.Next
}
return nil // Song not found
}i. Initialize Current Pointer
ii. Search for the Song:for current != nil {...} initiates a loop that continues until the end of the list is reached (i.e., current becomes nil).
Inside the loop, if current.Title == title {...} checks if the title of the current song matches the provided title.
iii. Move to the Next Node:current = current.Next moves the current pointer to the next node in the list, allowing the loop to continue the search.
5. Insert a Song at a Specific Position:
func (pl *Playlist) InsertSong(title, artist string, duration int, position int) {
newSong := &Song{Title: title, Artist: artist, Duration: duration, Next: nil}
if position == 1 {
newSong.Next = pl.Head
pl.Head = newSong
return
}
current := pl.Head
for i := 1; i < position-1 && current != nil; i++ {
current = current.Next
}
if current == nil {
return // Position exceeds the length of the playlist
}
newSong.Next = current.Next
current.Next = newSong
}Steps:
i. Create a New Song
ii. Insert at the Beginning:if position == 1 {...} checks if the desired position is at the beginning of the list.
If true, the new song is inserted at the beginning by updating newSong.Next to point to the current Head and making the new song the new Head. The method then returns.
iii. Traverse to the Desired Position:current := pl.Head initializes a pointer current to the Head of the list.for i := 1; i < position-1 && current != nil; i++ {...} iterates through the list until it reaches the node just before the desired position.
iv. Handle Position Exceeding Playlist Length:if current == nil {...} checks if the loop is completed without reaching the desired position. If so, the provided position exceeds the length of the playlist, and the method returns without making any changes.
v. Insert the New Song: newSong.Next = current.Next connects the new song to the node following the current node.
current.Next = newSong updates the Next field of the current node to point to the new song, effectively inserting it into the list.
6. Shuffle PlayList:
func (pl *Playlist) Shuffle() {
// Convert the linked list to an array
songs := make([]*Song, 0)
current := pl.Head
for current != nil {
songs = append(songs, current)
current = current.Next
}
// Shuffle the array
for i := len(songs) - 1; i > 0; i-- {
j := rand.Intn(i + 1)
songs[i], songs[j] = songs[j], songs[i]
}
// Rebuild the linked list
pl.Head = nil
for _, song := range songs {
song.Next = nil
pl.AddSong(song.Title, song.Artist, song.Duration)
}
}Steps:
i. Convert Linked List to Array:songs := make([]*Song, 0) initializes an empty array to store songs.current := pl.Head initializes a pointer current to the Head of the list.for current != nil {...} iterates through the list, appending each song to the array.
ii. Shuffle the Array:for i := len(songs) - 1; i > 0; i-- {...} iterates through the array in reverse order.
Inside the loop, j := rand.Intn(i + 1) generates a random index j between 0 and i.songs[i], songs[j] = songs[j], songs[i] swaps the songs at indices i and j, effectively shuffling the array randomly.
iii. Rebuild the Linked List:pl.Head = nil resets the Head of the linked list to nil.for _, song := range songs {...} iterates through the shuffled array.
Inside the loop, song.Next = nil disconnects the song from its original position in the list.
pl.AddSong(song.Title, song.Artist, song.Duration) adds the song back to the linked list in the new shuffled order.
7. Clear Playlist
func (pl *Playlist) Clear() {
pl.Head = nil
}8. Sort By Title
func (pl *Playlist) SortByTitle() {
if pl.Head == nil || pl.Head.Next == nil {
return // No need to sort if the playlist is empty or has only one element
}
sorted := false
for !sorted {
current := pl.Head
sorted = true
for current != nil && current.Next != nil {
if current.Title > current.Next.Title {
// Swap nodes
current.Title, current.Next.Title = current.Next.Title, current.Title
current.Artist, current.Next.Artist = current.Next.Artist, current.Artist
current.Duration, current.Next.Duration = current.Next.Duration, current.Duration
sorted = false
}
current = current.Next
}
}
}Steps:
i. Check for Empty or Single-Element Playlist:if pl.Head == nil || pl.Head.Next == nil {...} checks if the playlist is empty or has only one element. If so, there is no need to sort, and the method returns.
ii. Sorting:
The method uses the Bubble Sort algorithm to iteratively compare adjacent nodes and swap them if they are in the wrong order.
The outer loop (for !sorted {...}) continues until a pass through the list with no swaps, indicating that the list is sorted.
iii. Inner Loop (Comparison and Swap):current := pl.Head initializes a pointer current to the Head of the list.for current != nil && current.Next != nil {...} iterates through the list, comparing adjacent nodes.
If the title of the current song is greater than the title of the next song, it swaps the titles, artists, and durations, indicating a swap was made.sorted = false is set to indicate that a swap occurred, meaning the list might not be fully sorted.
