링크드 리스트란?
링크드 리스트(linkedlist)는 각각의 데이터가 노드(Node)로 구성되어 연결이 되있는 구조이다.
각각의 노드는 데이터와 함께 다음노드(next)와 이전노드(prev)를 가지고 있다.
노드는 linkedlist에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 중간에 데이터를 추가하거나 삭제해도 밀리거나 당겨지는 현상이 없기에 ArrayList에 비해 데이터의 추가나 삭제가 용이하나, 인덱스가 없어 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 해 오래 걸린다는 단점이 있고, 링크 필드로 인한 기억 공간이 많이 필요하다. 탐색/정렬을 많이 하는 경우는 배열을 사용하고 탐색/삭제를 많이 하는 경우에는 링크드 리스트를 사용하는 것이 좋다.
LinkedList 사용방법
선언
LinkedList list = new LinkedList(); // 타입 미설정 Object로 선언
LinkedList<Unit> units = new LinkedList<Unit>(); // 타입 설정, Unit객체만 사용 가능
LinkedList<Integer> num = new LinkedList<Integer>(); // 타입 설정, int 타입만 사용가능
LinkedList<Integer> num2 = new LinkedList(); // new에서 타입 파라미터 생략 가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2,3)); // 생성하는 동시에 값 추가
LinkedList선언 시 LinkedList list = new LinkedList()로 선언하고 내부의 임의의 값을 넣어서 사용할 수 있지만 이렇게 할 경우 값을 사용할 때마다 캐스팅(Casting)을 해야하고 번거롭기 때문에 위와같은 방법은 추천하지 않는다.
LinkedList를 생성 할 때 제너릭스를 이용해 사용 타입을 명시해 주는 것이 좋다.
값 추가
LinkedList<Integer> list3 = new LinkedList<Integer>();
list.addFirst(1); // 가장 앞에 데이터 추가
list.addLast(2); // 가장 뒤에 데이터 추가
list.add(3); // 데이터 추가
list.add(1,30); // index 1뒤에 데이터 30 추가LinkedList<Unit> list4 = new LinkedList<Unit>();
Unit unit = new Unit(50,"marine");
list4.add(unit);
LinkedList에 값을 추가하는 대표적인 방법으로 add(index, value) 메소드를 사용한다. index를 생략하면 가장 마지막 인덱스에 데이터가 추가된다. addFirst(int value) 메소드를 사용하게되면 가장 앞에 있는 Header의 값이 변경되고 addLast(int value) 메소드를 사용하면 제일 마지막 인덱스에 데이터가 추가된다.
값 삭제
LinkedList<Integer> l = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
l.removeFirst(); // 가장 앞의 데이터 제거
l.removeLast(); // 가장 뒤의 데이터 제거
l.remove(); // 0번째 index 제거
l.remove(2); // 2번째 index 제거
l.clear(); // 모든 값 제거
값을 삭제하는 방법은 값을 추가하는 방식이랑 비슷하다. removeFirst()는 가장 앞의 데이터를 제거하고 Last는 가장 뒤의 데이터를 제거한다. remove()는 제일 앞에있는 데이터를 제거하고 remove(int index)는 index의 데이터를 제거한다.
모든 데이터를 삭제하고 싶으면 clear() 메소드를 사용하면 된다.
크기 구하기
System.out.println(l.size()); // 크기 5
크기를 구하고 싶으면 size() 메소드를 사용하면 된다.
값 출력
System.out.println(l.get(2)); // 2번쨰 index 출력
for(Integer i : l) // for문을 통한 전체 출력
System.out.println(i);
Iterator<Integer> iter = l.iterator(); // Iterator 선언
while(iter.hasNext()) { // 다음 값이 있는지 체크
System.out.println(iter.next()); // 값을 출력
}
get(int index)메소드를 사용하면 해당되는 index의 data가 return된다. 전체 출력은 대부분 for을 통해서 출력을 하나 Iterator을 사용해서 출력 할 수 있다. LinkedList의 get(i) 메소드의 내부 동작은 순차 탐색으로 이루어져 있어 ArrayList의 get(i) 메소드보다 속도가 느리다.
값 검색
System.out.println(l.contains(1)); // l에 1이 있는지 검색
System.out.println(l.indexOf(1)); // 1이 있는 index 반환, 없으면 -1을 반환한다.
찾고자 하는 데이터의 값을 검색할려면 contains(int value) 메소드를 사용하면 된다. 리턴 값은 boolean으로 있으면 true, 없으면 false가 반환된다. 그리고 해당 데이터의 인덱스값을 알고 싶으면 indexOf(int value) 메소드를 사용하면 된다. 있으면 index를 반환하고 없으면 -1을 반환한다.