Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Что такое LinkedList и с чем его есть !

Автор: Akonkagva 7.11.2009, 21:19

Собственно начал изучать разницу между массивом и связанным листом и возник вопрос по тому как пользоваться им, хотелось бы конкретный простой примерчик(по LinkedList). Погуглив в нете я нашёл массу с примеров, но хм эти примеры они как будто бы с нуля создают связанный лист, который уже описан в документации((
Непонимаю почяму просто неиспользовать что то типо:

Код


LinkedList myList = new LinkedList();
LotteryMachine myLotteryMachine = null;
LotteryBall myLotteryBall = null;
myLotteryMachine = new LotteryMachine(); // создаём лотерейную машину
for (int i = 0; i < 6;i++)
{
  myLotteryBall =  myLotteryMachine.chooseBall(); // выбираем раннее невыбраный мячик ))
  myList.add(myLotteryBall);
}
for (int i = 0; i < 6;i++)
{
  Object val = myList.get(i); 
  myLotteryBall = (LotteryBall)val;
  print(myLotteryBall.getValue());
}

Ниже ресурсы откуда я черпал информацию...
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedList.html
http://www.theparticle.com/javadata2.html
Зачем использовать сверх сложные конструкции я непонимаю, возможно да и скорее всего я что-то недопонимаю...
Буду признателен за обьяснение !

Автор: duk 7.11.2009, 22:04

Akonkagva, так что Вам не понятно, если Вы сами написали пример использования списка?

Автор: Akonkagva 7.11.2009, 22:30

Мне непонятно зачем другие в качестве примеров используют столь сложные, нереально непонятные примеры...

Автор: duk 8.11.2009, 01:14

Я откуда знаю? Сами коллекции достаточно простые, чтоб разобраться с ними используя Java документацию.

Автор: ivanovpv 9.11.2009, 16:26

LinkedList он же связанный список = это пример списка, где элемент списка "знает" где находится следующий или предыдущий элемент списка. Массив не является связанным списком, поскольку элемент массива "не знает" кто является следующим за ним в списке. Правило обхода массива неявно задается индексом массива.

Связанные списки бывают однонаправленные (элемент знает следующего или предыдущего) и двунаправленные (элемент знает и предыдущего и последующего). В нутрях выглядит примерно так:

Код


class MyLinkedListElement
{
     private MyLinkedListElement next; //показывает на следующий элемент списка (в обычном списке этого указателя нет)
     private String blahblah;

     public MyLinkedListElement getNext() {return next;}
}

Стандартный java.util.LinkedList реализует двунаправленный связанный список. Уровень абстрагирования в стандартном java.util.LinkedList такой, что связанность списка видна только при использовании итератора, а так снаружи он выглядит как обычный список - где правило обхода фактически соответствует индексу списка.

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

Автор: sergioK 11.11.2009, 20:29

Цитата(Akonkagva @ 7.11.2009, 21:19)

Собственно начал изучать разницу между массивом и связанным листом и возник вопрос по тому как пользоваться им,

1, в массиве данные находяться последовательно в памяти , скажем нyлевой элемент по адресу АА00 первый AA04 - второй AA08 (т,е, прибавляеться кол-во байт
элемента массива )   в списке они разбросаны , т,е next - это поинтер на следующий элемент
2, внесение нового элемента или стирирание требует сдвигания массива , в ArrayList это делают за вас ,  т,е, происходит реалокация памяти , и делать это
   часто  то могут возникнуть проблемы , что бы избежать  это и был придуман LinkList,

   связаный список делает это одной операцией т,е O(1) а не O(n) ,

3, Советую почитать Керниган, Ричи , чтобы почувсвовать что такое LinkList

Вопрос не по теме , сегодня уже перестали преподавать С?  про асемблер я даже спрашивать боюсь   smile