Singly Linked List Data Structure in Python – Complete Tutorial with Examples

Step-by-Step Explanation

What This Program Does

This program creates a forward-only music playlist using a singly linked list. Each song points to the next song, so the playlist moves through tracks in order, like following a one-way road.

Creating a Song Node

class SongNode:
    def __init__(self, title):
        self.title = title
        self.next = None

SongNode represents one song in the playlist.

For example:

song = SongNode("Track 1")

creates:

[ Track 1 | None ]

Creating the Playlist

class ForwardOnlyPlaylist:
    def __init__(self):
        self.head = None
        self.current = None

The playlist uses two references:

At the beginning, the playlist is empty:

head → None
current → None

Adding a Song

def add_song(self, title):
    new_song = SongNode(title)

The add_song() method first creates a new song node with the supplied title.

Adding the First Song

if self.head is None:
    self.head = new_song
    self.current = new_song
    return

If the playlist is empty, the new song becomes both:

After adding the first track:

head ─┐
      ↓
[Track 1] → None
        ↑
current ┘

Adding More Songs

last = self.head

while last.next:
    last = last.next

When the playlist already contains songs, last starts at the first song. The loop follows each next reference until it reaches the final song.

last.next = new_song

The new song is connected after the last song.

For example:

Before:
[Track 1] → [Track 2] → None

After adding Track 3:
[Track 1] → [Track 2] → [Track 3] → None

Notice that current does not change when a new song is added. The playlist continues playing from its current position.

Playing the Next Song

def play_next(self):
    if self.current and self.current.next:
        self.current = self.current.next
    print(f"Now playing: {self.current.title}")

This method moves the playlist forward by one song.

if self.current and self.current.next:

The condition checks two things:

self.current = self.current.next

If both conditions are true, current moves to the next song.

print(f"Now playing: {self.current.title}")

The title of the current song is then printed.

Building the Playlist

playlist = ForwardOnlyPlaylist()

This creates an empty playlist:

head → None
current → None

Add Track 1

playlist.add_song("Track 1")

head ─┐
      ↓
[Track 1] → None
        ↑
current ┘

Both head and current point to Track 1.

Add Track 2

playlist.add_song("Track 2")

The new song is attached after Track 1:

head → [Track 1] → [Track 2] → None
        ↑
      current

current remains on Track 1.

Add Track 3

playlist.add_song("Track 3")

The new song is attached after Track 2:

head → [Track 1] → [Track 2] → [Track 3] → None
        ↑
      current

Playing the Tracks

First Call

playlist.play_next()

current moves from Track 1 to Track 2.

head → [Track 1] → [Track 2] → [Track 3] → None
                         ↑
                       current

Output:

Now playing: Track 2

Second Call

playlist.play_next()

current moves from Track 2 to Track 3.

head → [Track 1] → [Track 2] → [Track 3] → None
                                   ↑
                                 current

Output:

Now playing: Track 3

Example Trace

Important Details

The playlist is forward-only because each song stores only a next reference. There is no previous reference, so the program cannot move directly back to an earlier track.

The first song must update both head and current:

self.head = new_song
self.current = new_song

For later songs, only the final link changes. The current song should remain where it is until play_next() is called.

When the current song is the last song, self.current.next is None, so the condition fails and the current song remains unchanged.

Program Output

Now playing: Track 2
Now playing: Track 3

Summary: This program stores songs as linked nodes and moves through them one at a time by updating the current reference.

Step-by-Step Explanation

What This Program Does

This program creates a grocery list using a singly linked list. Each grocery item is stored in a node, and every node points to the next item, just like items connected in a shopping queue.

The program can add items, remove items, and display the current grocery list.

Creating an Item Node

class ItemNode:
    def __init__(self, item_name):
        self.item_name = item_name
        self.next = None

ItemNode represents one grocery item.

For example:

item = ItemNode("Milk")

creates:

[ Milk | None ]

Creating the Grocery List

class GroceryList:
    def __init__(self):
        self.head = None
        self.tail = None

The grocery list keeps two references:

At the beginning, the list is empty:

head → None
tail → None

Adding an Item

def add_item(self, item_name):
    new_item = ItemNode(item_name)

The add_item() method first creates a new node for the grocery item.

Adding the First Item

if self.head is None:
    self.head = new_item
    self.tail = new_item

If the list is empty, the new item becomes both the first and last item.

head ─┐
      ↓
   [Milk] → None
      ↑
tail ─┘

Adding More Items

else:
    self.tail.next = new_item
    self.tail = new_item

If items already exist:

For example:

Before:
head → [Milk] → [Eggs] → None
                         ↑
                        tail

After adding Bread:

head → [Milk] → [Eggs] → [Bread] → None
                                  ↑
                                 tail

Using tail makes it easy to attach a new item to the end without starting again from the head.

Removing an Item

def remove_item(self, item_name):
    if self.head is None:
        return False

If the grocery list is empty, there is nothing to remove, so the method returns False.

Removing the First Item

if self.head.item_name == item_name:
    self.head = self.head.next

If the first item matches, the head moves to the next item.

if self.head is None:
    self.tail = None
return True

If the removed item was the only item, the list is now empty. In that case, both head and tail must be set to None.

Before removing the only item:

head ─┐
      ↓
   [Milk] → None
      ↑
tail ─┘

After removing it:

head → None
tail → None

Removing a Middle or Last Item

current = self.head

while current.next is not None:
    if current.next.item_name == item_name:
        current.next = current.next.next

The method checks the node after current. If that next item matches, the current node skips over it.

For example:

Before:
[Milk] → [Eggs] → [Bread] → None

After removing Eggs:

[Milk] → [Bread] → None

The link from Milk now points directly to Bread.

Updating the Tail

if current.next is None:
    self.tail = current
return True

If the removed item was the last node, current.next becomes None. The code then updates tail so it points to the new final item.

If no matching item is found:

return False

The list remains unchanged.

Displaying the List

def show_list(self):
    current = self.head

The show_list() method starts at the head.

if current is None:
    print("Grocery list is empty!")
    return

If there are no items, it prints a message and stops.

current_item = current
items = []

An empty Python list is created to collect the grocery names.

while current_item is not None:
    items.append(current_item.item_name)
    current_item = current_item.next

The loop visits each node, saves its item name, and moves to the next node.

print("Grocery List:", " -> ".join(items))

The item names are joined with arrows and printed as one readable line.

Running the Example

shopping_list = GroceryList()

The list starts empty:

head → None
tail → None

Add the Items

shopping_list.add_item("Milk")
shopping_list.add_item("Eggs")
shopping_list.add_item("Bread")
shopping_list.add_item("Cucumber")

The list becomes:

head → [Milk] → [Eggs] → [Bread] → [Cucumber] → None
                                                    ↑
                                                   tail

Display the List

shopping_list.show_list()

Output:

Grocery List: Milk -> Eggs -> Bread -> Cucumber

Remove Eggs

shopping_list.remove_item("Eggs")

The node containing Eggs is skipped:

Before:
head → [Milk] → [Eggs] → [Bread] → [Cucumber] → None

After:
head → [Milk] → [Bread] → [Cucumber] → None

The tail still points to Cucumber because the removed item was in the middle.

Display the Updated List

shopping_list.show_list()

Output:

Grocery List: Milk -> Bread -> Cucumber

Example Trace

Important Details

Summary: This program manages a grocery list by adding, removing, and displaying items stored as connected nodes with head and tail references.

Step-by-Step Explanation

What This Program Does

This program creates a simple action log using a singly linked list. It records actions in the order they happen and later replays them from the first action to the last, like a timeline of file changes.

Creating an Action Node

class ActionNode:
    def __init__(self, action):
        self.action = action
        self.next = None

ActionNode represents one logged action.

For example:

node = ActionNode("Created file")

creates:

[ Created file | None ]

Creating the Action Log

class ActionLog:
    def __init__(self):
        self.head = None
        self.tail = None

The log keeps two references:

At the beginning, the log is empty:

head → None
tail → None

Recording an Action

def log_action(self, action):
    new_node = ActionNode(action)

The log_action() method creates a new node for the action being recorded.

Adding the First Action

if self.head is None:
    self.head = new_node
    self.tail = new_node

If the log is empty, the new action becomes both the first and last action.

head ─┐
      ↓
[Created file] → None
      ↑
tail ─┘

Adding Later Actions

else:
    self.tail.next = new_node
    self.tail = new_node

When actions already exist:

For example:

Before:
[Created file] → [Renamed file] → None
                                  ↑
                                 tail

After adding another action:

[Created file] → [Renamed file] → [Moved file to folder] → None
                                                           ↑
                                                          tail

The actions remain in the same order in which they were recorded.

Replaying the Actions

def replay_all(self):
    current = self.head

The replay_all() method starts at the first logged action.

while current is not None:

The loop continues while there is an action to process.

print(f"Replaying: {current.action}")

The current action is printed.

current = current.next

The program then moves to the next action in the chain. The loop stops after the final node, because its next value is None.

Running the Example

log = ActionLog()

The log starts empty:

head → None
tail → None

Record the First Action

log.log_action("Created file")

head ─┐
      ↓
[Created file] → None
      ↑
tail ─┘

Record the Second Action

log.log_action("Renamed file")

head → [Created file] → [Renamed file] → None
                       ↑
                      tail

Record the Third Action

log.log_action("Moved file to folder")

head → [Created file] → [Renamed file] → [Moved file to folder] → None
                                                                  ↑
                                                                 tail

Replay the Log

log.replay_all()

The method starts at head and follows each next reference.

Output:

Replaying: Created file
Replaying: Renamed file
Replaying: Moved file to folder

Example Trace

Important Details

The first action must update both head and tail:

self.head = new_node
self.tail = new_node

For later actions, only the old tail’s link and the tail reference need to change:

self.tail.next = new_node
self.tail = new_node

The log replays actions from oldest to newest because it always starts at head and follows the next links. It does not provide backward replay because each node stores only a forward reference.

If replay_all() is called on an empty log, the loop does not run and nothing is printed.

Summary: This program stores actions in a forward-linked timeline and replays them in the same order they were recorded.

Step-by-Step Explanation

What This Program Does

This program converts the words in a sentence into a singly linked list, prints them in their original order, reverses the links, and prints the words again. It is similar to arranging word cards in a line and then turning the line around so the last card comes first.

Creating a Word Node

class WordNode:
    def __init__(self, word):
        self.word = word
        self.next = None

WordNode represents one word in the linked list.

For example:

node = WordNode("I")

creates:

[ I | None ]

Building the Word List

def build_word_list(sentence):
    words = sentence.split()

The split() method separates the sentence into individual words.

"I am learning linked lists" becomes:

["I", "am", "learning", "linked", "lists"]

Creating the First Node

head = WordNode(words[0])
current = head

The first word is used to create the first node. head points to this node, and current is used to build the rest of the list.

head → [I] → None

Adding the Remaining Words

for word in words[1:]:
    current.next = WordNode(word)
    current = current.next

The loop processes every word after the first one.

current.next = WordNode(word)

A new node is created and connected after the current node.

current = current.next

current then moves to the new last node, ready for the next word.

After all words are added:

head → [I] → [am] → [learning] → [linked] → [lists] → None

return head

The function returns the first node so the complete linked list can be accessed.

Printing the Word List

def print_word_list(head):
    words = []
    current = head

The function starts at the head and creates an empty Python list to collect the words.

while current:
    words.append(current.word)
    current = current.next

For each node:

The loop stops when current becomes None.

print(" ".join(words))

The words are joined with spaces and printed as a sentence.

For the original list, the output is:

I am learning linked lists

Reversing the Word List

def reverse_word_list(head):
    previous = None
    current = head

The function uses two references:

At the beginning:

previous → None
current  → [I] → [am] → [learning] → [linked] → [lists] → None

Saving the Next Node

next_node = current.next

Before changing the current node’s link, the next node is saved. This is important because changing the link first could disconnect the rest of the list.

Reversing the Link

current.next = previous

The current node is redirected backward so it points to the previous node.

Moving the References Forward

previous = current
current = next_node

previous moves to the node just processed, and current moves to the next original node.

The complete loop is:

while current is not None:
    next_node = current.next
    current.next = previous
    previous = current
    current = next_node

When current becomes None, every link has been reversed.

return previous

At that point, previous points to the new first node.

Before and After

Before reversing:

head → [I] → [am] → [learning] → [linked] → [lists] → None

After reversing:

head → [lists] → [linked] → [learning] → [am] → [I] → None

The nodes are reused; only the direction of their next references changes.

Running the Example

sentence_list = build_word_list("I am learning linked lists")

This creates the linked list:

[I] → [am] → [learning] → [linked] → [lists] → None

print_word_list(sentence_list)

Output:

I am learning linked lists

reversed_list = reverse_word_list(sentence_list)

The links are reversed, and reversed_list receives the new head, which is the node containing "lists".

print_word_list(reversed_list)

Output:

lists linked learning am I

Example Trace

Important Details

The line below must come before changing current.next:

next_node = current.next

This preserves the connection to the remaining nodes.

The function returns previous, not the original head, because the original head becomes the last node after reversal.

The example assumes that the sentence contains at least one word. An empty sentence would produce an empty list of words, so words[0] would not have a word to use as the first node.

Summary: This program stores sentence words in a singly linked list, prints them in order, reverses the node links, and prints the sentence backwards.