1.3 LinkedList
배열은 가장기본적인 형태의 자료구조로 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 있다.
단점 1 : 크기를 변경 할 수 없다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
이를 보완하기 위해 링크드 리스트 자료구조가 고안되었다.
Class Node {
Node next; // 다음 요소의 주소 저장
Object obj; // 데이터를 저장.
}
LinkedList 클래스
- LinkedList() : LinkedList 객체 생성
- LinkedList(Collection c) : 주어진 컬렉션을 포함하는 LinkedList객체를 생성
- boolean add(Object o) : 지정된 객체(o)를 LinkedList의 끝에 추가, 저장에 성공하면 true, 실패하면 false
- void add(int index, Object element) : 지정된 위치(index)에 객체(element)를 추가
- boolean addAll(Collection c) : 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가한다. 성공하면 true, 실패하면 false
- boolean addAll(int index, Collection c) : 지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 추가. 성공하면 true, 실패하면 false
- void clear() : LinkedList의 모든 요소를 삭제
- boolean contains(Object c) : 지정된 객체가 LinkedList에 포함되었는지 알려줌
- boolean containsAll(Collection c) : 지정된 컬렉션의 모든 요소가 포함되었는지 알려줌
- Object get(int index) : 지정된 위치의 객체를 반환
- int indexOf(Object o) : 지정된 객체가 저장된 위치를 반환
- boolean isEmpty() : LinkedList가 비어있는지 알려준다. 비어있으면 true
- Iterator iterator() : Iterator를 반환한다.
- int lastindexOF(Object o) : 지정된 객체의 위치를 반환(끝부터 역순검색)
- ListIterator listiterator() : listIterator 를 반환
- ListIterator listiterator(int index) : 지정된 위치에서부터 시작하는 listIterator를 반환
- Object remove(int index) : 지정된 위치의 객체를 LinkedList에서 제거
- boolean remove(Object o) : 지정된 객체를 LinkedList에서 제거. 성공하면 true, 실패하면 false
- boolean removeAll(Collection c) : 지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
- boolean retainAll(Collection c) : 지정된 컬렉션의 모든 요소가 포함되어 있는지 확인.
- Object set(int index, Object element) : 지정된 위치의 객체를 주어진 객체로 바꿈
- int size() : LinkedList에 저장된 객체 수를 반환
- List subList(int fromindex, ind tolndex) : LinkedList의 일부를 list로 반환
- Object[] toArray() : LinkedList저장된 객체를 배열로 반환
- Object[] toArray(Object[] a) : LinkedList저장된 객체를 주어진 배열에 저장하여 반환
- Object element() : LinkedList의 첫 번째 요소를 반환
- boolean offer(Object o) : 지정된 객체 를 LinkedList의 끝에 추가, 성공하면 ture, 실패하면 false
- Object peek() : LinkedList의 첫 번째 요소를 반환
- Object poll() : LinkedList의 첫 번째 요소를 반환. LinkedList에서는 제거된다.
- Object remove() : LinkedList의 첫 번째 요소를 제거
- void addFirst(Object o) : LinkedList의 맨 앞의 객체를 추가
- void addLast(Object o) : LinkedList의 맨 끝의 객체를 추가.
- Iterator dexcendingiterator() : 역순으로 조회하기 위한 DescendingIterator를 반환
- Object getFirst() : LinkedList의 첫번째 요소를 반환
- Object getLast() : LinkedList의 마지막 요소를 반환
- boolean offerFirst(Object o) : LinkedList의 맨 앞에 객체를 추가 성공하면 true
- boolean offerLast(Object o) : LinkedList의 맨 뒤에 객체를 추가 성공하면 true
- Object peekFirst() : LinkedList의 첫번째 요소를 반환
- Object peekLast() : LinkedList의 마지막 요소를 반환
- Object pollFirst() : LinkedList의 첫번째 요소를 반환하면서 제거
- Object pollLast() : LinkedList의 마지막 요소를 반환하면서 제거
- Object pop() : removeFirst()와 동일
- void push(Object o) : addFirst()와 동일
- Object removeFirst() : LinkedList의 첫번째 요소를 제거
- Object removeLast() : LinkedList의 마지막 요소를 제거
- boolean removefirstOccurrence(Object o) : LinkedList에서 첫번쨰로 일치하는 객체를 제거
- boolean removeLastOccurrence(Object o) : LinkedList에서 마지막으로 일치하는 객체를 제거
실습1. ArrayList와 LinkedList 수행 속도 차이
package Collection_Framework;
import java.util.*;
public class LinkedList1 {
public static void main(String[] args) {
ArrayList a1 = new ArrayList(2000000);
ArrayList ll = new ArrayList();
System.out.println("=순차적으로 추가하기=");
System.out.println("ArrayList :"+add1(a1));
System.out.println("LinkedList :"+add1(ll));
System.out.println();
System.out.println("=중간에 추가하기=");
System.out.println("ArrayList :"+add2(a1));
System.out.println("LinkedList :"+add2(ll));
System.out.println();
System.out.println("=중간에서 삭제하기 =");
System.out.println("ArrayList :"+remove2(a1));
System.out.println("LinkedList :"+remove2(ll));
System.out.println();
System.out.println("=순차적으로 삭제하기=");
System.out.println("ArrayList :"+remove1(a1));
System.out.println("LinkedList :"+remove1(ll));
}
public static long add1(List list) {
long start = System.currentTimeMillis();
for(int i = 0; i<100000;i++)
list.add(i+"");
long end = System.currentTimeMillis();
return end -start;
}
public static long add2(List list) {
long start = System.currentTimeMillis();
for(int i = 0; i<10000;i++)
list.add(500,"X");
long end = System.currentTimeMillis();
return end -start;
}
public static long remove1(List list) {
long start = System.currentTimeMillis();
for(int i=list.size()-1;i>=0;i--)
list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
public static long remove2(List list) {
long start = System.currentTimeMillis();
for(int i=0;i<10000;i++)
list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
}
출력 결과 :
=순차적으로 추가하기=
ArrayList :62
LinkedList :49
=중간에 추가하기=
ArrayList :316
LinkedList :295
=중간에서 삭제하기 =
ArrayList :294
LinkedList :279
=순차적으로 삭제하기=
ArrayList :5
LinkedList :1
