@@ 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). |