Реализации алгоритмов/Связный список

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки на следующий и/или предыдущий узел списка.

Пример реализации односвязного списка на C

Заголовочный файл list.h:

#ifndef LIST_H
#define LIST_H

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
	int val;
	struct list *next;
}List;

static List* list_new(int val);
void list_add(List **list, int val);
void list_node_del(List **node);
void list_del_by_value(List **list, int val);
void list_free(List *list);

#endif

Файл list.c:

#include "list.h"

static List* list_new(int val) {
	List *list = (List*)malloc(sizeof(List));
	list->val = val;
	list->next = NULL;
	return list;
}

void list_add(List **list, int val) {
	for(; *list != NULL; list = &(*list)->next);
	*list = list_new(val);
}

void list_node_del(List **node) {
	free(*node);
	(*node) = (*node)->next;
}

void list_del_by_value(List **list, int val) {
	for(; *list != NULL; list = &(*list)->next) {
		if((*list)->val == val) {
			list_node_del(list);
			break;
		}
	}
}

void list_free(List *list) {
	for(; list != NULL; list = list->next)
		free(list);
}

Пример реализации на Java

public class Node {
  //содержимое текущего элемента списка
  private int element;
  //указатель на следующий элемент списка
  private Node next;
  //вывод содержимого текущего элемента
  public int getElement(){
    return element;
  }
  //установка содержимого для текущего элемента списка
  public void setElement(int e){
    element = e;
  }
  //получение указателя на следующий элемент списка
  public Node getNext() {
    return next;
  }
  //установка следующего элемента списка
  public void setNext(Node n) {
    next = n;
  }
}

Пример реализации односвязного списка на C#

class Node
    {
        public void SetNextNode(Node _nextNode)
        {
            this.next = _nextNode;
        }
        public int Element
        { 
            get
            {
                return this.element;
            }
            set
            {
                this.element = value;
            }
        }

        public Node Next
        {
            get
            {
                return this.next;
            }
        }

        private Node next;
        private int element;
    }

class List
    {
        public List()
        {
            // создание пустого списка
            this.headNode = null;
            this.tailNode = this.headNode;
            this.Length = 0;
        }
        public void Push(int _element)
        {
            if (headNode == null)
            {
                // создать узел, сделать его головным
                this.headNode = new Node();
                this.headNode.Element = _element;
                // этот же узел и является хвостовым
                this.tailNode = this.headNode;
                // следующего узла нет
                this.headNode.SetNextNode(null);
            }
            else
            {
                // создать временный узел
                Node newNode = new Node();
                // следующий за предыдущим хвостовым узлом - это наш временный новый узел
                this.tailNode.SetNextNode(newNode);
                // сделать его же новым хвостовым
                this.tailNode = newNode;
                this.tailNode.Element = _element;
                // следующего узла пока нет
                this.tailNode.SetNextNode(null);
            }

            ++this.Length;
        }
        public int this[int _position]
        {
            get
            {
                // дабы не загромождать пример, 
                // опустим проверку на валидность переданного параметра '_position'
                Node tempNode = this.headNode;
                for (int i = 0; i < _position; ++i)
                    // переходим к следующему узлу списка
                    tempNode = tempNode.Next;
                return tempNode.Element;
            }
        }

        public int Length { get; private set; }
        private Node headNode;
        private Node tailNode;
    }

Реализации на Pascal

Исправлено, работает!

type spisok=^element; //Сперва требуется обозначить список как тип
 element = Record //обозначаем элементы списка как запись, чтобы поместить туда данные и указатель на следующий элемент
 info:integer; //поле info отвечает за данные, которые хранит элемент списка (может быть любого типа)
 next:spisok; //так как список линейный, у нас будет указатель только на следующий элемент
end;

var first,elem,last:spisok; //создаём переменные начального элемента, вспомогательного элемента и конечного элемента типов список

 begin

 New(elem); //создаём новый элемент в динамической памяти
 elem^.next:=nil; //зануляем указатель на следующий элемент (так как его нету)
 elem^.info:=random(40)-20; //заполняем поле информации генератором рандома
 first:=elem;
 last:=elem; //так как элемент пока первый и последний, присваиваем оба элемента ему

// Процедура добавления элемента в конец списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=nil;
 last^.next:=elem; //следующий от последнего теперь наш элемент
 last:=elem; // и наш элемент и есть теперь последним

//Процедура добавления элемента в начало списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=first; //следующим есть первый элемент
 first:=elem; //наш элемент теперь первый

//Процедура удаления элемента с начала списка

 New(elem);
 elem:=first; //присваиваем нашему элементу значение первого
 first:=first^.next; //первым стал следующий элемент
 dispose(elem); //удаляем наш элемент

//Процедура удаления элемента с конца списка (тут потяжелее, так как список линейный)

 New(elem);
 elem:=first;
 while(elem^.next<>last) do
 begin //крутим цикл, пока не дойдем до элемента стоящего перед последним
 elem:=elem^.next; 
 elem^.next := nil; //делаем следующий от него элемент 0
 dispose(last); //удаляем последний элемент
 last:=elem; //теперь наш элемент последний
 end;

Пример реализации на Free Pascal

type spisok=^element; //Сперва требуется обозначить список как тип

element=record //обозначаем элементы списка как запись, чтобы поместить туда данные и указатель на следующий элемент
 info:integer; //поле info отвечает за данные, которые хранит элемент списка (может быть любого типа)
 next:spisok; //так как список линейный, у нас будет указатель только на следующий элемент
 end;

var p, first,elem,last:spisok; //создаём вспомогательную переменную элемента, переменные начального элемента, вспомогательного элемента и конечного элемента типов список

 begin

 New(elem); //создаём новый элемент в динамической памяти
 elem^.next:=nil; //зануляем указатель на следующий элемент (так как его нету)
 elem^.info:=random(40)-20; //заполняем поле информации генератором рандома
 first:=elem;
 last:=elem; //так как элемент пока первый и последний, присваиваем оба элемента ему

// Процедура добавления элемента в конец списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=nil;
 last^.next:=elem; //следующий от последнего теперь наш элемент
 last:=elem; // и наш элемент и есть теперь последним

//Процедура добавления элемента в начало списка

 New(elem);
 elem^.info:=random(40)-20;
 elem^.next:=first; //следующим есть первый элемент
 first:=elem; //наш элемент теперь первый

//Процедура удаления элемента с начала списка

 New(elem);
 elem:=first; //присваиваем нашему элементу значение первого
 first:=first^.next; //первым стал следующий элемент
 dispose(elem); //удаляем наш элемент

//Процедура удаления элемента с конца списка (тут потяжелее, так как список линейный)

 New(elem);
 elem:=first;
 while(elem^.next<>last) do //крутим цикл, пока не дойдем до элемента стоящего перед последним
 p:=elem^.next;
 elem^.next := nil; //делаем следующий от него элемент 0
 dispose(last); //удаляем последний элемент
 last:= p; //теперь наш элемент последний
 end.

Пример реализации на Haskell

List a = Nil |   a :+ (List a) deriving Show 
infixr 5  :+ 
-- пример создания списка
1 :+ 2 :+ Nil