Связный список на Golang

СТАТЬИ / СТРУКТУРЫ ДАННЫХ / СВЯЗНЫЙ СПИСОК НА 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.