Работа со структурами данных в языках Си и Python

Часть 2. Связные списки

Сергей Яковлев
Опубликовано 21.04.2011

В этой статье разбираются практические аспекты работы со связными списками - создание списка, добавление и удаление элементов, получение длины списка, сортировка списка и другие действия. Также в статье проводится тестирование производительности Python.

Массивы и связные списки

Связные списки используются, когда требуется структура данных, размер которой заранее неизвестен. В такие списки можно добавлять и удалять элементы уже после создания самого списка. Однако такой список требует дополнительных усилий для поддержания целостности при динамических операциях, так как при удалении элемента из списка обрывается связь между элементами, находящимися до и после него, и эти элементы необходимо снова связать между собой.

Списки широко используются в реальных проектах - операционных системах, базах данных, но для работы с ними требуется знать, как устроена арифметика указателей. В листинге 1 представлен массив из 100 элементов и инициализируются его первые 3 значения.

Листинг 1. Инициализация массива

int my_array[100];
my_array[0]=1;
my_array[1]=20;
my_array[2]=100;

Физически все 100 элементов располагаются в памяти последовательно, и индекс элемента - это смещение в блоке памяти от его начала, поэтому извлечение элемента по индексу выполняется крайне быстро. Это и есть адресная арифметика, но так как память для стандартного массива выделяется на этапе компиляции, то и модифицировать его впоследствии уже нельзя.

Для выделения памяти для связного списка используется иной механизм, когда память выделяется динамически, во время работы программы. Данный тип памяти называется «куча» (heap) и добавляемые элементы физически могут располагаться в такой куче без всякого упорядочивания.

Создание связного списка на языке Си

Элемент (узел) - это область памяти, в которой хранится ячейка связного списка. Узел односвязного списка состоит из 2-х полей: в первом хранятся данные (это поле также называется ключом), а во втором - указатель на следующий узел. Существует специальный указатель head, указывающий на первый узел списка. Указатель head – это отдельная переменная, не принадлежащая списку. Последний узел в списке указывает на NULL, и для него тоже создается специальная переменная - указатель tail. Если первый элемент указывает на NULL, то это будет пустой список. В листинге 2 приведена структура для определения элемента списка:

Листинг 2. Структура для элемента списка

struct node 
{
   int          data;
   struct node* next;
};

Указатель next имеет тот же тип, что и сам элемент, и указывает на следующий элемент списка. В листинге 3 приведен пример создания списка из трех элементов.

Листинг 3. Создание списка из трех элементов

// объявить три указателя на элементы списка
// указатель head ведет на первый элемент списка
	struct node* head = NULL;
	struct node* second = NULL;
	struct node* third = NULL;

// выделить память под элементы
//	метод sizeof вычисляет размер элемента
//	метод malloc выделяет требуемое количество памяти
// установить указатели на выделенные фрагменты памяти
	head   = malloc(sizeof(struct node));
	second = malloc(sizeof(struct node));
	third  = malloc(sizeof(struct node));

// инициализировать элементы списка и связать их между собой
	head->data = 1;
	head->next = second;
	second->data = 2;
	second->next = third;
	third->data = 3;
	third->next = NULL;

Создание связного списка в Python

В Python существует стандартная реализация списка, но ее не рекомендуется использовать из-за проблем с производительностью при выполнении динамических операций, о чем говорилось в прошлой статье. В листинге 4 представлен класс Node для определения элемента списка.

Листинг 4. Объявление элемента списка в Python

class Node:
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next

Для определения связного списка потребуется еще один класс – LinkedList, в конструкторе которого будут определяться первый и последний элементы списка и его длина. Также в классе будут использоваться встроенный метод str для распечатки содержимого списка и метод clear для очистки списка.

Листинг 5. Исходный код класса Linked List

import copy
import random 

class LinkedList:
    def __init__(self):
        self.first = None
        self.last = None
        self.length = 0

    def __str__(self):
        if self.first != None:
            current = self.first
            out = 'LinkedList [\n' +str(current.value) +'\n'
            while current.next != None:
                current = current.next
                out += str(current.value) + '\n'
            return out + ']'
        return 'LinkedList []'

    def clear(self):
        self.__init__()

//создание связного списка из 3-х элементов
L = LinkedList()
L.add(1)
L.add(2)
L.add(3)

Определение длины списка

Чтобы определить размер связного списка, необходимо пройти по списку и посчитать количество узлов. В листинге 6 приведена функция для подсчета числа узлов.

Листинг 6. Функция на языке Си для определения длины списка

	int Length(struct node* head) 
	{
		struct node* current = head;
		int count = 0;
		while (current != NULL) 
		{
				count++;
				current = current->next;
		}
		return count;
	}

В этой функции создается дополнительный указатель current, с помощью которого выполняется ИТЕРАЦИЯ связного списка:

	current = current->next;

При этой операции со списком ничего не происходит, но указателю НАЗНАЧАЕТСЯ новое значение. Если вызвать эту функцию для пустого списка, у которого вершина равна NULL, то функция вернет ноль. Для определения длины списка в Python используется функция Len (см. листинг 7), которая вначале проверяет, не является ли список пустым, а затем выполняет итерацию по элементам списка.

Листинг 7. Функция на языке Python для определения длины списка

    def Len(self):
        self.length =0
        if self.first != None:
            self.length +=1
            current = self.first
            while current.next != None:
                current = current.next
                self.length +=1
        return self.length

Добавление элемента в начало списка

В листинге 8 приведена функция Push для добавления элементов в начало списка в обратном порядке.

Листинг 8. Функция для добавления элементов в начало списка

void Push(struct node** headRef, int data) 
	{
		struct node* newNode = malloc(sizeof(struct node));
		newNode->data = data;
		newNode->next = *headRef;  
		*headRef = newNode;        
	}

// пример использования этой функции
struct node* head = NULL; // создание первого элемента
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);

Символ & - это указание компилятору, что параметр передается по ссылке, т.е. все изменения, которые будут сделаны с этим параметром внутри функции, останутся актуальными для переданного объекта и после выхода из функции. При передаче параметров по ссылке нужно следовать трем правилам:

1. в определении функции для указателей нужно использовать двойной указатель **;
2. при вызове функции перед ссылочным параметром нужно поставить &;
3. в самой функции к ссылочному параметру обращаться через указатель *.

Листинг 9. Реализация функции Push на языке Python

    def Push(self, x):
        if self.first == None:
            self.first = Node(x,None)
            self.last = self.first
        else:
            self.first = Node(x,self.first)

В Python-реализации учитываются два варианта: в первом случае список пуст, а во втором создается новый узел, в конструктор которого в качестве второго параметра передается головной элемент списка.

Добавление элементов в конец списка

В листинге 10 представлен пример добавления элементов в конец списка.

Листинг 10. Си – добавление элемента в конец списка

struct node* AppendNode(struct node** headRef, int num) 
{
   struct node* current = *headRef;
   struct node* newNode;
   newNode = malloc(sizeof(struct node));
   newNode->data = num;
   newNode->next = NULL;
   // если список пуст
   if (current == NULL) {
      *headRef = newNode;
   }
   else {
      // иначе
      while (current->next != NULL) {
          current = current->next;
      }
      current->next = newNode;
   }
}

В представленном коде выполняется итерация по списку для поиска последнего элемента, а затем его указатель next устанавливается на добавляемый элемент.

Листинг 11. Python - добавление элемента в конец списка

    def add(self, x):
        if self.first == None:
            self.first = Node(x, None)
            self.last = self.first
        elif self.last == self.first:
            self.last = Node(x, None)
            self.first.next = self.last
        else:
            current = Node(x, None)
            self.last.next = current
            self.last = current

Вставка элемента на определенную позицию в списке

Для вставки элемента в список необходимо передать указатель на головной элемент, индекс позиции, куда будет вставлен элемент, и, собственно, сам элемент. Если индекс равен нулю, то вызывается функция Push, в противном случае выполняется итерация, а затем снова происходит вызов Push.

Листинг 12. Си - вставка элемента в список

void InsertNth(struct node** headRef, int index, int data) 
{
  if (index == 0) Push(headRef, data);
  else 
  {
    struct node* current = *headRef;
    int i;
    for (i=0; i<index-1; i++) 
    {
      current = current->next;
    }
    Push(&(current->next), data); 
  }
}

В Python необходимо сначала проверить, что список не пуст, а затем, что вставка не происходит на нулевую позицию. Если оба условия не выполняются, то происходит итерация по списку до нужной позиции и добавление элемента:

Листинг 13. Python – вставка элемента в список

    def InsertNth(self,i,x):
        if (self.first == None):
            self.first = Node(x,self.first)
            self.last = self.first.next
            return
        if i == 0:
          self.first = Node(x,self.first)
          return
        curr=self.first
        count = 0
        while curr != None:
            if count == i-1:
              curr.next = Node(x,curr.next)
              if curr.next.next == None:
                self.last = curr.next
              break
            curr = curr.next

Удаление головного элемента

Функция Pop удаляет из списка головной узел, вместе с функцией Push она реализует функциональность стека, отцепляя головной элемент от списка и освобождая память. Функция принимает на вход двойной указатель на головной элемент, а возвращает значение удаленного элемента.

Листинг 14. Функция Pop – реализация на языке Си

int Pop(struct node ** head)
{
  struct node * temp = *head;
  int data=temp->data;
  *head = temp->next;
  free(temp);
  return data;
}

Для реализации на Python потребуется создать временную локальную переменную для хранения головного элемента. Если список не пустой, то головным узлом становится элемент, следующий за узлом, сохраненным во временной переменной.

Листинг 15. Функция Pop – реализация на Python

    def Pop(self):
        oldhead=self.first
        if oldhead==None:
            return None
        self.first=oldhead.next
        if self.first==None:
            self.last=None
        return oldhead.value

Удаление элемента из списка

В листинге 16 приведена реализация функции для удаления элемента из списка на языке Си.

Листинг 16. Си - удаление элемента из списка

int Del(struct node ** head,int index)
{
  int data = (*head)->data;
  if(index==0) Pop(head);
  else
  {
    int i;
    struct node * current = *head;
    for(i=0;i<index-1;i++)
      current=current->next;
    Pop(&(current->next));
  }
  return data;
};

В реализации для Python потребуется проверить список на пустоту и объявить две локальных переменных: первая будет хранить текущий элемент, а вторая - предыдущий. Потом выполняется итерация по списку для поиска удаляемого элемента и проверка того, не является ли он последним в списке. Если удаляемый элемент является последним, то предыдущий узел становится последним, в противном случае предыдущий узел связывается со следующим узлом вместо текущего.

Листинг 17. Python - удаление элемента из списка

    def Del(self,i):
        if (self.first == None):
          return
        old = curr = self.first
        count = 0
        if i == 0:
          self.first = self.first.next
          return
        while curr != None:
            if count == i:
              if curr.next == self.last:
                self.last = curr
                break
              else:
                old.next = curr.next 
              break
            old = curr  
            curr = curr.next
            count += 1

Вставка элемента в отсортированный список

В листинге 18 представлена функция для вставки элемента в отсортированный список. Как обычно, сначала выполняется проверка, что список не пустой, а затем итерация в поисках ближайшего элемента, значение которого меньше, чем у добавляемого.

Листинг 18. Си - вставка элемента в отсортированный список

void SortedInsert(struct node** headRef, struct node* newNode) 
{
  if (*headRef == NULL || (*headRef)->data >= newNode->data) 
  {
    newNode->next = *headRef;
    *headRef = newNode;
  }
  else 
  {
    struct node* current = *headRef;
    while (current->next!=NULL && current->next->data < newNode->data) 
    {
      current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
  }
}

В реализации на языке Python выполняется проверка списка на пустоту, а затем выполняется итерация с помощью двух временных переменных, как и в листинге 18.

Листинг 19. Python – вставка элемента в отсортированный список

    def SortedInsert(self,x):
        if (self.first == None):
          self.first = Node(x,self.last)
          return
        if self.first.value > x:
          self.first = Node(x,self.first)
          return
        old = curr = self.first
        while curr != None:
            if curr.value > x:
              curr = Node(x,curr)
              old.next = curr
              return
            old = curr
            curr = curr.next
        curr = Node(x,None)        
        old.next = curr

Удаление повторяющихся значений

Данная функция должна применяться к уже отсортированному списку. В качестве параметра в неё передается головной узел списка, и если в ходе итерации текущий элемент оказывается равным следующему за ним, то текущий элемент удаляется.

Листинг 20. Си – удаление повторяющихся значений

void RemoveDuplicates(struct node* head) 
{
  struct node* current = head;
  if (current == NULL) return;
  while(current->next!=NULL) 
  {
    if (current->data == current->next->data) 
    {
      struct node* nextNext = current->next->next;
      free(current->next);
      current->next = nextNext;
    }
    else 
    {
      current = current->next;
    }
  }
}

В версии на языке Python добавляется флаг, отмечающий наличие повторяющегося элемента. Этот флаг устанавливается при удалении повторяющегося элемента, и итерация прекращается, в противном случае итерация продолжается.

Листинг 21. Python – удаление повторяющихся значений

    def RemoveDuplicates(self):
        if (self.first == None):
            return
        old = curr = self.first
        while curr != None:
            _del = 0 
            if curr.next != None:
                if curr.value == curr.next.value:
                  curr.next = curr.next.next
                  _del = 1
            if _del == 0:
              curr = curr.next

Копирование списков

В листинге 22 показана функция для копирования списков. В ней используется три указателя: на первый элемент оригинального списка и на первый и последний элементы скопированного списка.

Листинг 22. Си – копирование списков

struct node* CopyList(struct node* head) 
{
   struct node* current = head; //первый элемент оригинального списка
   struct node* newList = NULL; //первый элемент нового списка
   struct node* tail = NULL; //последний элемент нового списка
   while (current != NULL) 
   {
      if (newList == NULL)  //создается первый элемент нового списка
      { 
         newList = malloc(sizeof(struct node));
         newList->data = current->data;
         newList->next = NULL;
         tail = newList;
      }
      else 
      {
         tail->next = malloc(sizeof(struct node));
         tail = tail->next;
         tail->data = current->data;
         tail->next = NULL;
      }
      current = current->next;
   }
   return(newList);
}

В листинге 23 приведена реализация этой же функциональности, но на основе рекурсии.

Листинг 23. Си - копирование списков на основе рекурсии

struct node* CopyList(struct node* head) 
{
   struct node* current = head;      
   if (head == NULL) return NULL;
   else 
	{
      struct node* newList = malloc(sizeof(struct node));   
      newList->data = current->data;
      newList->next = CopyList(current->next);  
      return(newList);
   }
}

В Python для копирования списков можно использовать стандартный модуль copy, как показано ниже.

import copy
L2 = copy.deepcopy(L) // создание копии списка L

Тестирование производительности

Для тестирования производительности связных списков использовался список, состоящий из 2000 элементов, при этом значение элемента могло быть от 0 до 100, и элементы вставлялись в отсортированном порядке.

В ходе тестирования было выяснено, что реализация одного и того же алгоритма для вставки элементов в отсортированный связный список ведет себя по-разному в зависимости от языка и размера списка. Производительность Python-реализации начинает снижаться, когда в списке накапливается более 2-х тысяч элементов. Анализ результатов теста показывает, что основные потери процессорного времени происходят во время итерации.

Исходный код тестов на языках Си и Python можно найти в архиве performance_benchmark.zip, прикрепленном к статье. Реализация на языке Си работает гораздо быстрее, и ее производительность начинает снижаться, когда размер списка становится значительно больше 2-х тысяч элементов. Версию на языке Python не спасает даже оптимизация кода за счет сокращения вызовов функции SortedInser, так как из-за динамического создания объектов в Python, начиная с определенного момента, возникают проблемы при итерации.

Заключение

Как было показано в этой статье, связные списки предоставляют богатый набор функций для добавления и удаления элементов, сортировки, копирования и других операций. Поэтому связные списки являются «краеугольным камнем» и первой ступенью для изучения других структур данных связного типа.

Ресурсы для скачивания

• этот контент в PDF

Похожие темы

• Работа со структурами данных в языках Си и Python. Часть 1.
• Работа со структурами данных в языках Си и Python. Часть 2.