생활코딩 DataStructure -4

1. ArrayList Iterator 메서드 구현

 

1-1. previous()

 - next() 메서드를 실행하면, 실행당시 nextIndex값을 리턴 한후 nextindex에 +1을 하기 때문에, 다음 값을 가르키고 있는 상태가 된다, 따라서 previous()코드는 nextindex의 값을 리턴하기 전에 -1을 하여, 처음에 맨 끝값을 출력하고 다음부터 이전 값을 출력하게 된다. (처음에 맨 끝값을 출력하는 이유는 next()마지막 수행이 현재 elementData에 담고 있는 마지막 element를 출력하고 마지막 엘리먼트의 다음 index값을 가르키고 있기 떄문에 previous()를 처음 실행할 땐 elementData의 마지막 값을 출력한다.

public Object previous() {
	return elementData[--nextIndex];
}



System.out.println(li.previous());

 

1-2. hasPrevious()

 - next() <-> hasNext()의 관계와 비슷하게, previous도 끝까지 출력하다가 더이상 출력할 수 없는 index: -1까지 갈경우 오류를 출력하게됨.

 - hasPrevious를 통해 그 범위를 명시해야 함. ( indexSize가 0일 때는 previous()실행시 idexSize가 -1인 elementData의 요소를 출력하라는 지시를 하기 때문에 오류가 난다. 따라서 indexSize > 0에서만 previous()가 실행될 수 있도록 지정해 주어야 한다.)

while (li.hasPrevious()) {
	System.out.println(li.previous());
}

public boolean hasPrevious(){
	return indexsize > 0;
}

 

1-3 Iterator add

 - Iterator 클래스 안에서 add의 기능을 만들어 줄때, Iterator를 담고있는 class인 ArrayList class에서 정의된 기존의 add함수를 사용해서 메서드를 정의 할 수 있다. (객체지향 프로그래밍)

 - 이때, ArrayList의 add를 재사용하면, 메서드의 이름이 겹치기 때문에, ArrayList.this.add() : this 키워드를 통해 이 메서드는 ArrayList의 add메서드라는 것을 명시한다. ( 사용하고자하는 메서드가 속해 있는 필드 . this . 메서드이름)

while (li.hasNext()) {
	int number = (int)li.next();
    if (number == 30){
    	li.add(35);
    }
}

public void add(Object element){
	ArrayList.this.add(nexIndex++, element)
}

 

 

1.4 Iterator remove()

 - add메서드의 생성과 마찬가지로 ArrayList의 remove()함수를 사용하여 간편하게 정의 (this키워드 사용)

 - ArrayList.this.remove(nextIndex-1); next()를 실행한 순간 nextIndex는 다음 index를 가르키고 있기 때문에 next()실행 이후 현재 자료를 삭제하고 싶으면 nextIndex-1을 해주어야 한다.

 - nextIndex--; : 이후 인덱스에 -1을 하여 삭제되었음을 표시한다 

public void remove() {
			ArrayList.this.remove(nextIndex-1);
			nextIndex--;
}


while (li.hasNext()) {
			int number = (int)li.next();
			if(number == 30) {
				li.remove();
			}
}

2. Linked List

 - List를 만드는 2가지 방법중 하나. (ArrayList , Linked List)

 - Linked = 연결 (연결을 어떻게 프로그래밍적으로 표현하는가와 관련)

 

2-1 cpu, memory, storage

 - Linked List이해하기 위해서는 필수적으로memory를 알아야 함.

 - storage(하드디스크 등)는 느리지만, 용량이 많은 특징을 지님. memory는 빠르지만 용량이 적음. storage에 저장되어 있는 파일이나 프로그램은 memory를 커져 cpu가 처리하게 됨.

 - 따라서 컴퓨터의 동작에 있어 memory가 중요하기 때문에 memory를 어떻게 효율적으로 이용하여 프로그램을 빠르고, 용이하게 처리해야하는 것이 중요. (datastructure의 중요성이자 필요성)

 

2-2 memory의 데이터저장 특징  

 - memory에는 각각 주소가있고, 주소에는 데이터가 저장되어 있음

 - memory의 각각의 주소에 도달하는 시간은 전부 동일 함 (Random access memory = RAM)

 - 즉, Adress(주소)를 알고 있다면, 빠르게 정보를 가져올 수 있음

 

 2-3 memory상에서 ArrayList와 Linked List의 데이터가 저장된 구조 차이

2-4 LinkedList의 구조

 - LinkedList는 ArrayList와는 다르게 연결이라는 특성을 지니기 때문에, 내부적으로 element라는 이름 대신, node(마디) 또는 vertex(정점, 꼭지점)라는 개념을 사용 (연결을 나타내기위한 표현)

 - 객체지향 프로그래밍 언어에서는 객체를 통해 node를 표현. node안에는 두개의 필드(변수)가 존재. 첫 번째 변수는 저장되는 실제의 값(data field), 두 번째 변수는 다음 노드가 무엇인가라는 정보가 저장되있는 주소(Link field)임

 - HEAD: 첫 번째 node가 무엇인지를 나타내는 변수. 첫번째 노드를 알아야 Link field를 통해 다음 node에 연결할 수 있으므로 LinkedLisk에서 head의 위치를 필수적으로 알아야함.

 

* 노트필기랑 같이보기

( Linked list 개념 6 - Array list VS Linked list - Data Structure 까지)