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