Doubly Linked List Algorithm
The Doubly Linked List Node Algorithm is a data structure that allows for the efficient manipulation and organization of elements in a dynamic list. Each node in a doubly linked list contains three components: the data element itself, a reference to the previous node in the list, and a reference to the next node in the list. This bidirectional linking of nodes enables traversal and modification of the list in both directions, which provides greater flexibility and functionality in comparison to its simpler counterpart, the singly linked list.
In the Doubly Linked List Node Algorithm, insertion and deletion operations can be performed easily, without needing to traverse the entire list, as long as the target node is known. To insert a new node, the algorithm simply updates the pointers of the adjacent nodes, creating a connection between the new node and its neighbors. Similarly, to delete a node, the algorithm modifies the pointers of the neighboring nodes to bypass the target node, effectively removing it from the list. Despite the benefits of bidirectional traversal and improved manipulation capabilities, doubly linked lists do incur a slight overhead in terms of memory usage, as each node requires storage for two pointers rather than one. However, this trade-off is often deemed acceptable in applications where frequent modifications and versatile traversal capabilities are essential.
package DoublyLinkedList
type Node struct {
data int
next *Node
prev *Node
}
type LinkedList struct {
head *Node
tail *Node
}
func (list *LinkedList) InsertFirst(i int) {
data := &Node{data: i}
if list.head != nil {
list.head.prev = data
data.next = list.head
}
list.head = data
}
func (list *LinkedList) InsertLast(i int) {
data := &Node{data: i}
if list.head == nil {
list.head = data
list.tail = data
return
}
if list.tail != nil {
list.tail.next = data
data.prev = list.tail
}
list.tail = data
}
func (list *LinkedList) RemoveByValue(i int) bool {
if list.head == nil {
return false
}
if list.head.data == i {
list.head = list.head.next
list.head.prev = nil
return true
}
if list.tail.data == i {
list.tail = list.tail.prev
list.tail.next = nil
return true
}
current := list.head
for current.next != nil {
if current.next.data == i {
if current.next.next != nil {
current.next.next.prev = current
}
current.next = current.next.next
return true
}
current = current.next
}
return false
}
func (list *LinkedList) RemoveByIndex(i int) bool {
if list.head == nil {
return false
}
if i < 0 {
return false
}
if i == 0 {
list.head.prev = nil
list.head = list.head.next
return true
}
current := list.head
for u := 1; u < i; u++ {
if current.next.next == nil {
return false
}
current = current.next
}
if current.next.next != nil {
current.next.next.prev = current
}
current.next = current.next.next
return true
}
func (list *LinkedList) SearchValue(i int) bool {
if list.head == nil {
return false
}
current := list.head
for current != nil {
if current.data == i {
return true
}
current = current.next
}
return false
}
func (list *LinkedList) GetFirst() (int, bool) {
if list.head == nil {
return 0, false
}
return list.head.data, true
}
func (list *LinkedList) GetLast() (int, bool) {
if list.head == nil {
return 0, false
}
current := list.head
for current.next != nil {
current = current.next
}
return current.data, true
}
func (list *LinkedList) GetSize() int {
count := 0
current := list.head
for current != nil {
count += 1
current = current.next
}
return count
}
func (list *LinkedList) GetItemsFromStart() []int {
var items []int
current := list.head
for current != nil {
items = append(items, current.data)
current = current.next
}
return items
}
func (list *LinkedList) GetItemsFromEnd() []int {
var items []int
current := list.tail
for current != nil {
items = append(items, current.data)
current = current.prev
}
return items
}