Содержание
Связный список на Golang
В предыдущей статье мы рассмотрели, чем отличается связный список от массива.
Теперь давайте посмотрим, как написать его на языке Go и протестируем время работы.
Базовый элемент
Элемент однонаправленного связного списка должен содержать непосредственно данные и ссылку на следующий элемент.
Для его реализации хорошо подойдет структура (struct). Объявим новый тип, содержащий в себе данные в формате int и ссылку на следующий элемент:
type element struct {
data int
next *element
}
Теперь реализуем функцию создания нового связного списка:
func genNewList(data int) element {
return element{data, nil}
}
Здесь мы иициализировали новую структуру, в которой данные взяли из переданного параметра, а ссылку на следующий элемент оставили пустой.
Обратите внимание, функция возвращает только первый элемент!
Печать всего списка
Реализуем функцию печати всего содержимого списка:
func printList(list *element) {
for {
fmt.Println(list.data)
if list.next != nil {
list = list.next
} else {
break
}
}
}
Здесь мы принимаем ссылку на первый элемент массива и запускам цикл, в котором:
- печатаем содержимое поля с данными элемента;
- проверяем, есть ли ссылка на следующий элемент:
- если он есть — делаем его главным и позвращаемся в начало массива;
- если ее нет — завершаем цикл.
Проверим, что все работает. Создадим новый элемент в теле функции main() и выведем его содержимое:
func main() {
list := genNewList(0)
printList(&list)
}
Результат:
0
Все сработало, мы распечаали первый элемент списка.
Функции добавления элементов
Добавить элементы в список можно с разных сторон. И, как мы помним из сравнения его с массивом, это главная особенность и положительная сторона связного списка — возможность быстро добавить элементы в любую его часть. Рассмотрим три варианта.
Добавление элемента в конец списка
Для добавления элемента в конец списка нам понадобится дойти до нужного элемента и просто присвоить его полю next ссылку на новый элемент.
func addToEnd(list *element, data int) {
for {
if list.next != nil {
list = list.next
} else {
list.next = &element{data: data, next: nil}
break
}
}
}
Здесь мы точно так же проходим по всему списку в цикле, и когда добираемся до последнего элемента — присваиваем полю next ссылку на только что созданный новый элемент.
Проверим, что все отрабатывает, распечатав содержимое списка:
func main() {
list := genNewList(0)
addToEnd(&list, 5)
printList(&list)
}
Результат:
0
5
В конец списка добавлен новый элемент со значением 5.
Добавление элемента в начало списка
Теперь добавить элемент в начало списка. Процедура аналогично предыдущей, только здесь сначала создается новый элемент, а потом к нему добавляется ссылка на предыдущий первый элемент списка, ставший теперь вторым.
Посколько в качестве ссылки на список у нас хранится только ссылка на первый элемент, функция добавления будет возвращать ссылку на новый первый элемент списка, которой мы заменим исходную.
func addToStart(list element, data int) element {
newList := element{data: data, next: &list}
return newList
}
Проверим, что все работает.
func main() {
list := genNewList(0)
addToEnd(&list, 5)
list = addToStart(list, 10)
printList(&list)
}
Результат:
10
0
5
Добавление элемента в тело списка
Для добавления элемента в середину списка нужно дойти до предыдущего элемента, добавить ему ссылку на новый, а в новом добавить ссылку на следующий.
func addAfter(list *element, index int, data int) {
counter := 0
for {
if counter != index {
if list.next != nil {
counter++
list = list.next
} else {
fmt.Println("The specified index goes beyond the bounds of the list!")
break
}
} else {
newElement := element{data: data, next: list.next}
list.next = &newElement
break
}
}
}
Здесь мы вводим дополнительный счетчик, который считает итерации прохода по списку. Как только он дошел до нужного индекса — ссылка в элементе заменяется на новый элемент, ссылка на следующий в котором ведет на следующий элемент, который был ранее. Цикл завершается.
Проверим, что все работает:
func main() {
list := genNewList(0)
addToEnd(&list, 5)
list = addToStart(list, 10)
addAfter(&list, 1, 20)
printList(&list)
}
Результат:
10
0
20
5
Проверим, что при превышении размера выводится предупреждение:
addAfter(&list, 5, 20)
Результат:
The specified index goes beyond the bounds of the list!
10
0
5
Сообщение выведено, список остался неизменным.
Удаление элементов
Добавление мы рассмотрели, теперь осталось рассмотреть удаление элементов.
Удаление последнего элемента
Здесь все по аналогии с добавлением, только теперь у предпоследнего элемента нужно заменить ссылку на nil.
func delLast(list *element) {
for {
if list.next != nil {
list = list.next
if list.next.next == nil {
list.next = nil
break
}
}
}
}
Проверяем результат:
delLast(&list)
printList(&list)
Результат:
10
0
Удаление первого элемента
Здесь тоже все просто: нужно вернуть ссылку на второй элемент (если он есть).
func delFirst(list *element) element {
if list.next != nil {
return *list.next
} else {
fmt.Println("There is nothing to delete!")
}
return *list
}
Проверим:
list = delFirst(&list)
printList(&list)
Результат:
0
Удаление элемента в теле списка
Все аналогично удалению первого элемента, только до «первого» элемента сначала нужно дойти.
func delAfter(list *element, index int) {
counter := 0
for {
if counter != index {
if list.next != nil {
counter++
list = list.next
} else {
fmt.Println("The specified index goes beyond the bounds of the list!")
break
}
} else {
list.next = list.next.next
break
}
}
}
Проверим, что все работает (на предыдущем списке их трех элементов):
delAfter(&list, 0)
printList(&list)
Результат:
10
5
Удален средний (второй) элемент.
Здесь тонкость: мы указали индекс 0, т.к. хотим удалить второй по счету элемент. Т.к. нумерация класиически начинается с 0, вторым будет элемент с индексом 1, то есть идущий после 0. В функции мы удаляем именно элемент после заданного.
Весь код целиком
Ну и по классике весь код целиком:
package main
import (
"fmt"
)
type element struct {
data int
next *element
}
func genNewList(data int) element {
return element{data, nil}
}
func printList(list *element) {
for {
fmt.Println(list.data)
if list.next != nil {
list = list.next
} else {
break
}
}
}
func addToEnd(list *element, data int) {
for {
if list.next != nil {
list = list.next
} else {
list.next = &element{data: data, next: nil}
break
}
}
}
func addToStart(list element, data int) element {
newList := element{data: data, next: &list}
return newList
}
func addAfter(list *element, index int, data int) {
counter := 0
for {
if counter != index {
if list.next != nil {
counter++
list = list.next
} else {
fmt.Println("The specified index goes beyond the bounds of the list!")
break
}
} else {
newElement := element{data: data, next: list.next}
list.next = &newElement
break
}
}
}
func delLast(list *element) {
for {
if list.next != nil {
list = list.next
if list.next.next == nil {
list.next = nil
break
}
}
}
}
func delFirst(list *element) element {
if list.next != nil {
return *list.next
} else {
fmt.Println("There is nothing to delete!")
}
return *list
}
func delAfter(list *element, index int) {
counter := 0
for {
if counter != index {
if list.next != nil {
counter++
list = list.next
} else {
fmt.Println("The specified index goes beyond the bounds of the list!")
break
}
} else {
list.next = list.next.next
break
}
}
}
func main() {
list := genNewList(0)
addToEnd(&list, 5)
list = addToStart(list, 10)
addAfter(&list, 5, 20)
printList(&list)
fmt.Println("---")
delAfter(&list, 0)
printList(&list)
}
Также исходники доступны в репозитории на GitHub.