>>
Связанный список Наука Наука 

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

admin

Связанный список представляет собой линейную последовательность объектов, называемых узлами, узлы соединены между собой посредством ссылок.

Как правило, программа получает доступ к связанному списку через первый элемент списка. Доступ к каждому последующему элементу осуществляется через ссылку, сохраненную в предыдущем узле. По соглашению, ссылка в последнем узле устанавливается в NULL для обозначения конца списка. Данные хранятся в связанном списке динамически, т.е. программа создает для каждый следующий узел по мере необходимости. Узел может содержать данные любого типа, включая ссылки на объекты других классов. Стеки и очереди являются также линейными структуры данных и представляют собой ограниченный вариант связанных списков. Деревья — это нелинейные структуры данных.

Данные последовательности могут храниться в массивах, но связные списки обеспечивают ряд преимуществ. Связанный список-это уместно, если число элементов данных, которые будут представлены в структуре данных непредсказуем. Связные списки являются динамическими, поэтому длина списка может увеличиваться или уменьшаться по мере необходимости. Размер «обычного» массива в java не может быть изменен, потому что размер массива фиксируется в тот момент, когда программа создает массив.

Пакет java.util содержит класс LinkedList для реализации и управления связанными списками, которые расширяются или уменьшаются по ходу выполнения программы.

В этом примере рассмотрим действия со связанными списками.

package java1;
 

  import java.util.List;
  import java.util.LinkedList;
  import java.util.ListIterator;
 
  public class Test
 {
     private static final String stringarray[] = { "Moscow", "Paris",
       "Zurich", "Budapest", "Praha", "Wien" };
    private static final String stringarray2[] = { "Pekin", "Tokio",
       "Sydney", "Kair", "Berlin", "Toronto" };

    
    public Test()
     {
       List< String > list1 = new LinkedList< String >();
        List< String > list2 = new LinkedList< String >();

       // добавим элементы в список
       for ( String sity : stringarray )
          list1.add( sity );

       // add elements to list link2
       for ( String sity : stringarray2 )
           list2.add( sity );

        list1.addAll( list2 ); // совмещение списков
        list2 = null; // освобождение ресурсов
       printList( list1 ); // печать элементов списка list1

        convertToUppercaseStrings( list1 ); // перевод в верхний регистр
       printList( list1 ); // печать элементов списка list1

        System.out.print( "\nDeleting elements 2 to 6..." );
        removeItems( list1, 2, 7 ); // удалить элементы 2-7 из списка
        printList( list1 ); // печать элементов списка list1
       printReversedList( list1 ); // печать элементов списка list1 в обратном порядке
     } // конец конструктора класса

     // метод вывода на печать
     public void printList( List< String > list )
     {
       System.out.println( "\nlist: " );

        for ( String sity : list )
          System.out.printf( "%s ", sity );

       System.out.println();
    } // конец метода вывода на печать

     // метод перевода в верхний регистр
     private void convertToUppercaseStrings( List< String > list )
    {
       ListIterator< String > iterator = list.listIterator();

       while ( iterator.hasNext() )
       {
          String sity = iterator.next();                   
          iterator.set( sity.toUpperCase() ); // конвертировать в верхний регистр
       } // end while
    } 

    // создать дочерний список и используя метод clear удалить элементы
     private void removeItems( List< String > list, int start, int end )
    {
        list.subList( start, end ).clear();  // удалить элементы
    } 

    // метод печати элементов в обратном порядке
    private void printReversedList( List< String > list )
    {
       ListIterator< String > iterator = list.listIterator( list.size() );

       System.out.println( "\nReversed List:" );

       // напечатать список в обратном порядке
       while ( iterator.hasPrevious() )
           System.out.printf( "%s ", iterator.previous() );
    } // end method printReversedList

     public static void main( String args[] )
    {
       new Test();
    } // end main
  } // конец класса Test

Результат выполнения программы:

list: 
Moscow Paris Zurich Budapest Praha Wien Pekin Tokio Sydney Kair Berlin Toronto 

list: 
MOSCOW PARIS ZURICH BUDAPEST PRAHA WIEN PEKIN TOKIO SYDNEY KAIR BERLIN TORONTO 

Deleting elements 2 to 6...
list: 
MOSCOW PARIS TOKIO SYDNEY KAIR BERLIN TORONTO 

Reversed List:
TORONTO BERLIN KAIR SYDNEY TOKIO PARIS MOSCOW

 

Похожие записи