SiroDiaz /
DataStructures
| @@ 59-88 (lines=30) @@ | ||
| 56 | * @return mixed The data stored in the given index |
|
| 57 | * @throws OutOfBoundsException if index is out bounds. |
|
| 58 | */ |
|
| 59 | public function get($index) { |
|
| 60 | if($index < 0 || $index > $this->size - 1) { |
|
| 61 | throw new OutOfBoundsException(); |
|
| 62 | } |
|
| 63 | ||
| 64 | if($index === 0) { |
|
| 65 | return $this->head->data; |
|
| 66 | } |
|
| 67 | ||
| 68 | if($index === $this->size - 1) { |
|
| 69 | return $this->tail->data; |
|
| 70 | } |
|
| 71 | ||
| 72 | $current = &$this->head; |
|
| 73 | if($index < (int) ceil($this->size / 2)) { |
|
| 74 | $i = 0; |
|
| 75 | while($i < $index) { |
|
| 76 | $current = &$current->next; |
|
| 77 | $i++; |
|
| 78 | } |
|
| 79 | } else { |
|
| 80 | $i = $this->size; |
|
| 81 | while($i > $index) { |
|
| 82 | $current = &$current->prev; |
|
| 83 | $i--; |
|
| 84 | } |
|
| 85 | } |
|
| 86 | ||
| 87 | return $current->data; |
|
| 88 | } |
|
| 89 | ||
| 90 | /** |
|
| 91 | * Gets the node stored in the position especified. |
|
| @@ 98-127 (lines=30) @@ | ||
| 95 | * @throws OutOfBoundsException if it is out of limits (< 0 or > size - 1) |
|
| 96 | * @return DataStructures\Lists\Nodes\DoublyLinkedListNode|null the node stored in $index. |
|
| 97 | */ |
|
| 98 | protected function search($index) { |
|
| 99 | if($index < 0 || $index > $this->size - 1) { |
|
| 100 | throw new OutOfBoundsException(); |
|
| 101 | } |
|
| 102 | ||
| 103 | if($index === 0) { |
|
| 104 | return $this->head; |
|
| 105 | } |
|
| 106 | ||
| 107 | if($index === $this->size - 1) { |
|
| 108 | return $this->tail; |
|
| 109 | } |
|
| 110 | ||
| 111 | $current = &$this->head; |
|
| 112 | if($index < (int) ceil($this->size / 2)) { |
|
| 113 | $i = 0; |
|
| 114 | while($i < $index) { |
|
| 115 | $current = &$current->next; |
|
| 116 | $i++; |
|
| 117 | } |
|
| 118 | } else { |
|
| 119 | $i = $this->size; |
|
| 120 | while($i > $index) { |
|
| 121 | $current = &$current->prev; |
|
| 122 | $i--; |
|
| 123 | } |
|
| 124 | } |
|
| 125 | ||
| 126 | return $current; |
|
| 127 | } |
|
| 128 | ||
| 129 | /** |
|
| 130 | * Returns the data in the last node with O(1). |
|
