생활코딩 DataStructure -6

1. LinkedList에서 ListIterator 생성.

public ListIterator listIterator() {
		return new ListIterator();
	}
		
		class ListIterator{
			private Node next;
			private Node lastReturned;
			private int nextIndex;
			
			ListIterator(){
				next = head;
			}
            
            

//Main에서 호출 
LinkedList.ListIterator i = numbers.listIterator();

 

2. ListIterator next() 구현 

 -next()를 실행하면, lastReturned노드의 데이터 값을 리턴하고, next변수를 통해 다음 값을 가르킨다.

 -nextIndex++를 통해 내부적으로 index를 유지한다.

 

public Object next() {
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.data;
		}
			

 

3. ListIterator hasNext() 구현

 - LinkedList에 담긴 총 size와 비교하여, size보다 작다면 아직 tail에 도달하지 않은 것 이기 때문에 출력할 값이 있다는 표시의 true를 출력.

 

		public boolean hasNext() {
			return nextIndex < size();
		}

 

4. add() 구현 

 - next()를 통해 LinkedList의 요소를 반복하는 작업을 수행할 때, 현재 next가 리턴한데이터(lastReturned.data)의 다음 에 값을 넣어주는 함수

- lastReturned = newNode; : add를 실행한 행위도, next()와 같이 다음 값으로 넘어간 행위로 간주. 

 

		public void add(Object input) {
			Node newNode = new Node(input);
			
			if(lastReturned == null) { //아직 값이 아무것도 없다. 
				head = newNode;
				newNode.next = next;
			} else {
				lastReturned.next = newNode;
				newNode.next = next;
			}
			
			lastReturned = newNode; // 즉, lastReturned 값은 현재값이다.
			nextIndex++;
			size++;
		}

 

5. remove() 구현 

 - LinkedList의 remove함수는 자체적으로 node()라는 함수를 사용하여 link를 찾고 있기 때문에, 이 방법으로 remove를 실행하면, 시간이 오래걸리는 단점이 있다. 따라서 자체적으로 이전값을 나타내는 변수를 유지하면서 지워주는게 효율적인데, 이는 doubleLinkedlist에서 살펴본다.

		public void remove() {
			if(nextIndex == 0) { //remove()는 lastReturned 값을 삭제하는데, 한번도 next가 실행되지 않았다면, remove()할 값도 없다는 뜻. 
				throw new IllegalStateException();
			}
			LinkedList.this.remove(nextIndex-1); 
			nextIndex--;
				
			}

 

6. ArrayList vs LinkedList

 - LinkedList는 값의 추가와 삭제가 빠르다 ( ArrayList는 한칸씩 전부 옮겨야 해서 느리다) 

 - ArrayList는 내부적으로 배열을 사용하기 때문에 indext를 이용하여 get으로 값을 가져오는 것이 빠르다 ( LinkedList는 get하고자하는 data를 앞에서부터 링크로 찾아야 하기 때문에 느리다)