Листа (структура података)

Из Википедије, слободне енциклопедије

Листа је структура података која се одликује линеарним распоредом припадајућих елемената. По својој природи, листа је најсроднија низу, али се углавном имплементира користећи динамичко алоцирање меморије и показиваче.

Особине[уреди]

Свака листа мора да задовољава сљедеће особине:

  • Листа може бити празна
  • Могуће је убацити нови елемент на било коју позицију у листи
  • Могуће је избацити било који елемент из листе
  • Листа има своју величину, тј. број елемената
  • Сваком елементу листе се може приступити преко редног броја, тј. индекса

Листа се може састојати од елемената различитих типова, а може бити типизирана, тј. имати ограничење да сви припадајући елементи морају бити истог, одређеног унапријед, типа.

Врсте[уреди]

ListePodataka.png

По врсти повезаности, листе се најчешће дијеле на једноструко повезане и двоструко повезане. По свом облику, дијеле се на линеарне и кружне листе.

Двоструко повезане листе су листе по којима је могуће претраживање припадајућих елемената у два смјера. Ово се у програмирању најчешће имплементира постојањем два показивача у сваком елементу листе, од којих један показује на претходни, а други на сљедећи елемент у листи. Ова врста листе је јако удобна за рад, и у већини случајева олакшава рјешење у односу на једноструко повезану листу.

Једноструко повезане листе подржавају претраживање елемената само у једном смјеру. Код имплементација листе помоћу показивача и динамичке меморије, сваки елемент садржи по тачно један показивач који показује на сљедећи елемент у листи. Најчешће се користе у ситуацијама када је једносмјерно претраживање довољно за дати проблем. Иако ограничене једним смјером, оне имају уштеду од по једног показивача по елементу што, у случајевима са великим бројем елемената, може бити значајно.

Кружне листе се одликују одсуством почетка листе. Наиме, за разлику од обичних листи које имају јасно изражен почетни елемент и крајњи елемент, чији показивач је једнак нули, последње убачени елемент листе се увијек поставља да показује на први, а први елемент може да шета, тј. у сваком тренутку било који елемент може да се прогласи за први без ремећења структуре. На овај начин се постиже да се итерација по листи не мора никада завршити, једноставно прелазећи сваки пут на сљедећи елемент, што чини одређене алгоритме једноставнијим.

Види још[уреди]

Спољашње везе[уреди]