Aprende Building Doubly Linked Lists | Linear Data Structures

Desliza para mostrar el menú

Introduction to Doubly Linked Lists

A doubly linked list is a type of linear data structure where each element, called a node, contains three parts:

Data: the value or information stored in the node;
Next pointer: a reference to the next node in the sequence;
Previous pointer: a reference to the previous node in the sequence.

This structure allows you to move forward and backward through the list efficiently.

Key Concepts and Terminology

Node: a container that holds data and two pointers (next and prev).
Head: the first node in the list; its prev pointer is always nil.
Tail: the last node in the list; its next pointer is always nil.
Next pointer (next): points to the next node in the list.
Previous pointer (prev): points to the previous node in the list.

How Doubly Linked Lists Differ from Singly Linked Lists

In a singly linked list, each node only stores a next pointer, so you can only move forward through the list;
In a doubly linked list, each node stores both next and prev pointers, which lets you move both forward and backward;
Inserting or deleting nodes in a doubly linked list is more flexible, especially when you need to remove nodes from the end or middle of the list.

Doubly linked lists are especially useful for applications where you need quick access in both directions, such as in navigation systems, undo/redo features, or managing browser history.

main.go


              1234567891011121314151617181920212223242526272829303132333435363738394041
            
package main

import "fmt"

// Node represents a node in a doubly linked list
type Node struct {
    data int
    prev *Node
    next *Node
}

func main() {
    // Initialize three nodes
    first := &Node{data: 10}
    second := &Node{data: 20}
    third := &Node{data: 30}

    // Link the nodes together
    first.next = second
    second.prev = first
    second.next = third
    third.prev = second

    // Print the list forward
    fmt.Println("Traverse forward:")
    current := first
    for current != nil {
        fmt.Printf("%d ", current.data)
        current = current.next
    }
    fmt.Println()

    // Print the list backward
    fmt.Println("Traverse backward:")
    current = third
    for current != nil {
        fmt.Printf("%d ", current.data)
        current = current.prev
    }
    fmt.Println()
}

Adding Elements to a Doubly Linked List

To add an element to a doubly linked list, you need to update the links between nodes so the new element is correctly inserted. Each node in a doubly linked list contains a value, a pointer to the next node, and a pointer to the previous node. This structure allows you to insert elements efficiently at the beginning, end, or any position in the list.

Steps to Add a Node

Create a new node with the desired value;
Set the new node's next pointer to the node that will follow it;
Set the new node's prev pointer to the node that will precede it;
Update the next pointer of the previous node to point to the new node;
Update the prev pointer of the next node to point to the new node;
If inserting at the beginning, update the list's head pointer to the new node;
If inserting at the end, update the list's tail pointer to the new node.

This process ensures that the list remains connected in both directions, and you can traverse it forward or backward from any node.

main.go


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
            
package main

import (
	"fmt"
)

type Node struct {
	data int
	prev *Node
	next *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
}

func (dll *DoublyLinkedList) InsertAtBeginning(data int) {
	newNode := &Node{data: data}
	if dll.head == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}
	newNode.next = dll.head
	dll.head.prev = newNode
	dll.head = newNode
}

func (dll *DoublyLinkedList) InsertAtEnd(data int) {
	newNode := &Node{data: data}
	if dll.tail == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}
	dll.tail.next = newNode
	newNode.prev = dll.tail
	dll.tail = newNode
}

func (dll *DoublyLinkedList) PrintForward() {
	current := dll.head
	for current != nil {
		fmt.Printf("%d ", current.data)
		current = current.next
	}
	fmt.Println()
}

func main() {
	dll := DoublyLinkedList{}

	dll.InsertAtEnd(10)
	dll.InsertAtBeginning(5)
	dll.InsertAtEnd(15)
	dll.InsertAtBeginning(2)

	fmt.Print("Doubly linked list (forward): ")
	dll.PrintForward()
}

Removing Elements from a Doubly Linked List

Removing an element from a doubly linked list involves updating the links between nodes to exclude the node you want to remove. Since each node has both a next and a prev pointer, you can efficiently remove a node from any position in the list—whether it is at the beginning, end, or somewhere in the middle.

Steps to Remove a Node

Identify the node you want to remove;
Update the next pointer of the node's previous node to point to the node's next node;
Update the prev pointer of the node's next node to point to the node's previous node;
If the node is the head (first node), update the head reference to the next node;
If the node is the tail (last node), update the tail reference to the previous node.

This process ensures the list remains connected after removal, and no references are left pointing to the removed node. You can then safely delete or ignore the removed node, allowing Go's garbage collector to reclaim its memory.

main.go


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
            
package main

import (
	"fmt"
)

type Node struct {
	data int
	next *Node
	prev *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
}

func (dll *DoublyLinkedList) Append(data int) {
	node := &Node{data: data}
	if dll.head == nil {
		dll.head = node
		dll.tail = node
		return
	}
	dll.tail.next = node
	node.prev = dll.tail
	dll.tail = node
}

func (dll *DoublyLinkedList) RemoveFromBeginning() {
	if dll.head == nil {
		fmt.Println("List is empty; nothing to remove.")
		return
	}
	fmt.Printf("Removing %d from the beginning.\n", dll.head.data)
	dll.head = dll.head.next
	if dll.head != nil {
		dll.head.prev = nil
	} else {
		dll.tail = nil
	}
}

func (dll *DoublyLinkedList) RemoveNode(target *Node) {
	if target == nil {
		fmt.Println("Target node is nil; nothing to remove.")
		return
	}
	if target.prev != nil {
		target.prev.next = target.next
	} else {
		dll.head = target.next
	}
	if target.next != nil {
		target.next.prev = target.prev
	} else {
		dll.tail = target.prev
	}
	fmt.Printf("Removed node with value %d.\n", target.data)
}

func (dll *DoublyLinkedList) Find(data int) *Node {
	current := dll.head
	for current != nil {
		if current.data == data {
			return current
		}
		current = current.next
	}
	return nil
}

func (dll *DoublyLinkedList) Print() {
	current := dll.head
	for current != nil {
		fmt.Printf("%d ", current.data)
		current = current.next
	}
	fmt.Println()
}

func main() {
	dll := &DoublyLinkedList{}
	dll.Append(10)
	dll.Append(20)
	dll.Append(30)
	dll.Append(40)
	fmt.Print("Initial list: ")
	dll.Print()

	// Remove from beginning
	dll.RemoveFromBeginning()
	fmt.Print("After removing from beginning: ")
	dll.Print()

	// Remove a specific node (value 30)
	target := dll.Find(30)
	dll.RemoveNode(target)
	fmt.Print("After removing node with value 30: ")
	dll.Print()
}

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 2. Capítulo 2

Pregunte a AI

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Sección 2. Capítulo 2