JAVA 개발자 수업 27일차 - 연결 리스트(LinkedList), iterator

1. 연결 리스트(LinkedList)

2. iterator

---

1. 연결 리스트(LinkedList)

[정의]

- 각 Node가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조.

- 데이터를 담고 있는 Node들이 연결되어 있고, Node의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다.

- Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다.

- List 인터페이스를 구현했기때문에 ArrayList와 사용법 유사(내부 구조는 다르다.)

 

출처: https://pridiot.tistory.com/66

 

[ArrayList & LinkedList Append(추가) 비교]

ArrayList<Integer> arr = new ArraryList<Integer>();
LinkedList<Integer> list = new LinkedList<Integer>();

long begin=0;
long end=0;

//순차적으로 데이터 추가 - ArrayList
begin = System.currentTimeMillis() //tick값

for (int i=0; i<1000000; i++) {
    arr.add(i);
}

end = System.currentTimeMillis()
System.out.println("ArrayList 작업시간: %,dms\n", end - begin);

//순차적으로 데이터 추가 - LinkedList
begin = System.currentTimeMillis(); //tick

for (int i=0; i<1000000; i++) {
    list.add(i);
}

end = System.currentTimeMillis(); //tick
System.out.printf("LinkedList 작업시간: %,dms\n", end - begin);


//OUTPUT
ArrayList 작업시간: 30ms
LinkedList 작업시간: 149ms

----> 순차적인 데이터 추가는 ArrayList가 LinkedList보다 빠르다.

 

[ArrayList & LinkedList Insert(삽입) 비교]

ArrayList<Integer> arr = new ArrayList<Integer>();
LinkedList<Integer> list = new LinkedList<Integer>();

//배열 중간에 데이터 추가 - ArrayList
begin = System.currentTimeMillis();

for (int i=0; i<10000; i++) {
    arr.add(0, i);
}
		
end = System.currentTimeMillis(); 
System.out.printf("ArrayList 작업시간: %,dms\n", end - begin);
		
//배열 중간에 데이터 추가 - LinkedList
begin = System.currentTimeMillis(); 

for (int i=0; i<10000; i++) {
    list.add(0, i);
}

end = System.currentTimeMillis();
System.out.printf("LinkedList 작업시간: %,dms\n", end - begin);


//OUTPUT
ArrayList 작업시간: 4,640ms
LinkedList 작업시간: 1ms

----> 중간 데이터 추가는 LinkedList가 ArrayList보다 압도적으로 빠르다.

 

[ArrayList & LinkedList Delete(삭제) 비교]

ArrayList<Integer> arr = new ArrayList<Integer>();
LinkedList<Integer> list = new LinkedList<Integer>();

//순차적으로 데이터 삭제(끝->처음) - ArrayList
begin = System.currentTimeMillis();

for (int i=list1.size()-1; i>=0; i--) {
    arr.remove(i);
}
		
end = System.currentTimeMillis(); 
System.out.printf("ArrayList 작업시간: %,dms\n", end - begin);
		
//순차적으로 데이터 삭제(끝->처음) - LinkedList
begin = System.currentTimeMillis(); 

for (int i=list1.size()-1; i>=0; i--) {
    list.remove(i);
}

end = System.currentTimeMillis();
System.out.printf("LinkedList 작업시간: %,dms\n", end - begin);


//OUTPUT
ArrayList 작업시간: 7ms
LinkedList 작업시간: 28ms

----> 순차적인 데이터 삭제는 ArrayList가 LinkedList보다 빠르다.

 

[ArrayList & LinkedList 장,단점]

	장점	단점
ArrayList	모든 컬렉션을 통틀어 특정 요소에 접근 속도가 가장 빠르다.	요소의 추가, 삭제 작업 비용이 많이 든다.
LinkedList	- ArrayList 단점이 곧 장점 - 요소의 추가, 삭제 작업 비용이 저렴하다.	- ArrayList 장점이 곧 단점 - 특정 요소에 접근 속도가 느리다.

- ArrayList와 LinkedList는 서로 상반된다.

- 읽기 작업을 많이 한다면 ArrayList

- 쓰기 작업을 많이 한다면 LinkedList

 

2. iterator

[정의]

- 컬렉션에 저장된 요소를 접근(탐색)하는데 사용되는 인터페이스이다.

- 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화 -> Iterator인터페이스

-  Collection 인터페이스를 상속받는 List와 Set 인터페이스에서도 iterator() 사용 가능

 

[Iterator 메서드]

boolean hasNext()//읽어올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false
Object next() 	 //다음 요소를 읽어온다. next()호출 전, hasNext()를 호출해서 확인하는것이 안전하다.
void remove() 	 //next()로 읽어온 요소를 삭제한다.

 

[ArrayList에서의 iterator]

ArrayList<String> list = new ArrayList<String>();

list.add("사과");
list.add("바나나");
list.add("딸기");
list.add("포도");
list.add("귤");
list.add("복숭아");
list.add("참외");

list.iterator();
Iterator<String> iter = list.iterator();

while(iter.hasNext()) {
    System.out.println(iter.next());
}


//OUTPUT
사과
바나나
딸기
포도
귤
복숭아
참외

 

<HashMap에서의 iterator>

HashMap<String, String> map = new HashMap<String, String>();
map.put("과장", "홍길동");
map.put("사원", "아무개");
map.put("대리", "하하하");
map.put("부장", "호호호");

Set<String> set = map.keySet(); //Key 집합 반환
Iterator<String> iter = set.iterator();

while (iter.hasNext()) {
    String key = iter.next();
    
    System.out.println(key); //key값
    System.out.println(map.get(key)); //value값
}


//OUTPUT
부장
호호호
대리
하하하
과장
홍길동
사원
아무개

----> 뒤죽박죽 섞인것은 HashMap 특성상 어쩔 수 없다.
----> HashMap에서의 탐색(iterator)는 키, 값을 나눠서 따로따로 받아야함. > Set

---

MEMO>

# ArrayList와 LinkedList 어떤것을 쓸지 판단하기는 실질적으로 힘들지만, 보편적으로 읽기작업이 많아서, ArrayList가 많이 쓰인다.

 

# 컬렉션에서의 탐색 방법은 이전에는 for문, 향상된 for문을 이용했는데 오늘 배운 iterator를 잘 사용해야겠다.

 

# 일주일간의 첫번째 프로젝트가 2일차 진입. 화이팅!