List, ArrayList, Vector, LinkedList 가 있습니다

Presentation on theme: "List, ArrayList, Vector, LinkedList 가 있습니다"— Presentation transcript:

1 자바는 Collection 프레이머라 하는 데이터스트럭쳐(Data Structure, 자료구조)를 제공하고 있고, Collection 안에
List, ArrayList, Vector, LinkedList 가 있습니다. 링크드리스트는 ArrayList와 동일한 리스트라고 하는 인터페이스를 구현하고 있기 때문에 두 개의 사용방법 다른 말로는 API 또는 다른 말로는 메소드의 이름 또는 형태 이런 것들은 거의 비숫합니다.. 기본적으로 두 리스트는 사용 방법은 똑 같지만 중요한 것은 이 두 개의 클래스가 내부적인 구현 방법이 서로 다르다는 것입니다.

2 Node / Vertex / element Data field Link field ArrayList는 내부적으로 배열 사용을 하는 것에 비해서, LinkedList는 객체를 만들고, 객체와 객체를 연결(reference) 하여 구현. ArrayList와 LinkedList는 API가 거의 유사하다. 서로 사용방법은 유사하지만, 클래스의 내부적인 구현 방법이 서로 다르다.

3 SIZE : 현재 몇 개의 노드가 이 리스트 안에 포함되어 있는가라는 정보가 담겨있다.
Node / Vertex / element 마지막에 있는 노드의 정보를 가지는 Tail 이 Tail 정보는 유지할 수도 아닐 수도 있음! Data Tail HEAD Link Variable, 이다음 리스트가 누구인지에 대한 정보를 담고 있다 즉, 이다음 리스트에 대한 reference(연결)의 값의 정보를 가지고 있다 누가 첫 번째 노드인가?라는 정보를 알려주는 변수를 가지고 있어야 함. 바로 HEAD

4 HEAD TAIL SIZE 1 새로 만들어진 노드 새로 만들어진 노드가 이전의 노드의 HEAD값을 참조할 수 있다.
Ex) newNode.next = head;

5 HEAD TAIL SIZE 2 새로 만들어진 노드 새로 만들어진 노드가 이전의 노드의 HEAD값을 참조할 수 있다.
Ex) newNode.next = head;

6 HEAD TAIL SIZE 3 새로 만들어진 노드 새로 만들어진 노드가 이전의 노드의 HEAD값을 참조할 수 있다.
Ex) newNode.next = head;

7

8 HEAD TAIL SIZE 3 next 처음 새로 만들어진 노드 마지막 노드 새로 생선된 노드
추가법:마지막에 있는 노드가 새로 생성된 노드를 가리키게 하면 된다. Tail 변수가 가리키는 노드 즉, 새로 생성한 노드를 next로 하면, 새로 생성한 노드 즉, 이 엘리먼트 리스트의 맨 마지막에 추가되는 효과. 즉, tail이 가리키는 노드는 이제 새로게 생성된 노드가 된다.

9 HEAD TAIL SIZE 3 next 처음 새로 만들어진 노드 마지막 노드 새로 생선된 노드
추가법:마지막에 있는 노드가 새로 생성된 노드를 가리키게 하면 된다. Tail 변수가 가리키는 노드 즉, 새로 생성한 노드를 next로 하면, 새로 생성한 노드 즉, 이 엘리먼트 리스트의 맨 마지막에 추가되는 효과. 즉, tail이 가리키는 노드는 이제 새롭게 생성된 노드가 된다.

10 HEAD TAIL SIZE 3 tail.next = newNode; tail = newNode; next
처음 새로 만들어진 노드 마지막 노드 새로 생선된 노드 추가법:마지막에 있는 노드가 새로 생성된 노드를 가리키게 하면 된다. Tail 변수가 가리키는 노드 즉, 새로 생성한 노드를 next로 하면, 새로 생성한 노드 즉, 이 엘리먼트 리스트의 맨 마지막에 추가되는 효과. 즉, tail이 가리키는 노드는 이제 새로게 생성된 노드가 된다.

11

12 HEAD TAIL SIZE 3 next 새로 추가될 노드 (인덱스 1)
처음 새로 만들어진 노드 (인덱스 0) temp1 두 번째 노드 (인덱스 1) (인덱스 2) temp2 새로 추가시 생선된 노드 (인덱스 2) (인덱스 3) 새로 추가될 노드 (인덱스 1) 노드와 노드 사이 추가법 : 추가된 후 추가된 노드는 인덱스 값이 1이 되고, 두 번째 노드는 인덱스 값이 2가 됨. 현재 구인덱스 1인 두 번째 노드에 새로운 노드를 추가 하려하는데, 이전 노드의 값(인덱스)를 알고 있어야 되는데 첫 번째 노드가 새로 추가될 노드를 가리키게 해야 되고, 새로 추가된 노드는 구1인텍스 노드를 가리키게 해야 된다. 즉, 현재 첫 번째 노드가 새로 추가될 노드를 가리키게 하려면, 첫 번째 노드(0인덱스)를 알아야 된다. 즉, 0인덱스를 알아야 하는 이유는 새로 추가될 노드를 next로 지정해야 되기 때문이다. 다시말해서, temp1의 next(노드)가 새로 추가될 노드를 가리키게 한다[temp1.next = newNode;] 새로 추가될 노드 즉, newNode의 next(노드)가 temp2를 가리키게 한다[newNode.next = temp2;]

13 HEAD TAIL SIZE 4 next 새로 추가될 노드 (인덱스 1)
처음 새로 만들어진 노드 (인덱스 0) temp1 두 번째 노드 (인덱스 1) (인덱스 2) temp2 새로 추가시 생선된 노드 (인덱스 2) (인덱스 3) 새로 추가될 노드 (인덱스 1) 노드와 노드 사이 추가법 : 추가된 후 추가된 노드는 인덱스 값이 1이 되고, 두 번째 노드는 인덱스 값이 2가 됨. 현재 구인덱스 1인 두 번째 노드에 새로운 노드를 추가 하려하는데, 이전 노드의 값(인덱스)를 알고 있어야 되는데 첫 번째 노드가 새로 추가될 노드를 가리키게 해야 되고, 새로 추가된 노드는 구1인텍스 노드를 가리키게 해야 된다. 즉, 현재 첫 번째 노드가 새로 추가될 노드를 가리키게 하려면, 첫 번째 노드(0인덱스)를 알아야 된다. 즉, 0인덱스를 알아야 하는 이유는 새로 추가될 노드를 next로 지정해야 되기 때문이다. 다시말해서, temp1의 next(노드)가 새로 추가될 노드를 가리키게 한다[ex)temp1.next = newNode;] 새로 추가될 노드 즉, newNode의 next(노드)가 temp2를 가리키게 한다[ex)newNode.next = temp2;]