Collection Framwork 1.3 LinkedList

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