Java :: Collection :: 1.3 LinkedList

김병철·2022년 9월 1일
1

Java

목록 보기
3/20

Java의 정석 3판을 보며 공부한 내용을 정리하였습니다.
남궁성님께 많이 배우고 있습니다.

1.3 LinkedList

# 배열의 장점

  • 간단한 구조
  • 쉽게 사용 가능
  • 데이터를 읽는 데 걸리는 시간이 빠르다.

# 배열의 단점

  • 크기 변경 불가능
  • 비순차적인 데이터의 추가 및 삭제에 시간이 많이 걸린다.

# 링크드리스트

이런 단점을 보완하는 자료구조가 바로 !! 링크드 리스트(Linked list)!!!

그림 1. 배열과 링크드 리스트

위 그림과 같이 링크드 리스트는 각 노드(node)가 자신과 연결될 다음 노드의 주소값과 데이터를 갖는다.

class Node{
	Node	next;	// 다음 노드의 주소
    Object	obj;	// 데이터

# 링크드 리스트의 데이터 추가

그림 2. 링크드 리스트에서의 데이터 추가

예를 들어 다음과 같이 노드가 있다고 해보자.

A-> B-> C-> D-> E

A는 B의 주소를 갖고 있고, B는 C, C는 D, ...

만약 여기서 F를 B와 C사이에 넣고 싶다면!

A-> B-> F-> C-> D-> E

위와 같이 B가 다음 노드로 F의 주소를 갖고
F는 C의 주소를 가지면 된다.
그럼 삭제는 어떻게 할까 ?

# 링크드 리스트의 데이터 삭제

그림 3. 링크드 리스트에서의 데이터 삭제

마찬가지로 앞에 연결했던 노드에 뒤 노드의 주소를 저장해서 이어주면 된다.


더블 링크드 리스트(이중 연결리스트; doubly linked list)

링크드 리스트가 단방향인데 그러면 양쪽으로 연결하면 어떨까?

그림 4. 더블 링크드 리스트(doubly linked list)

그게 바로 더블 링크드 리스트(이중 연결리스트; doubly linked list)이다.

class Node{
	Node	next;		// 다음 노드의 주소
    Node	previous;	// 이전 노드의 주소
    Object	obj;		// 데이터

링크드 리스트에서 이전 노드의 추소만 추가된 것이다.


더블 써큘러 링크드 리스트(이중 원형 연결리스트; doubly circular linked list)

여기서 한 발짝 더 나아간다면?

A - B - C - D - E - A

이렇게 순환 구조로는 어떻게 하면 될까?
가장 마지막 노드(E)에 다음 노드 주소값으로 A를 넣어주면 된다.
마찬가지로 첫 노드(A)에 이전 노드 주소값으로 E를 넣으면 순환 구조가 된다.

이 자료구조는 더블 써큘러 링크드 리스트(이중 원형 연결리스트; doubly circular linked list)이다.


LinkedList의 생성자와 메서드

  • LinkdList()
    -> 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)
    -> 지정된 위치(index)에 주어진 컬렉션에 포함된 모든 요소를 추가. 성공 시 true, 실패 시 false
  • void clear()
    -> LinkedList 의 모든 요소 삭제
  • boolean contains(Object o)
    -> 지정된 객체가 LinkedList에 포함되었는지 알려줌
  • boolean containsAll(Collection c)
    -> 지정된 컬렉션의 모든 요소가 포함되었는지 알려줌
  • Object get(int index)
    -> 지정된 위치(index)의 객체를 반환
  • int indexOf(Object o)
    -> 지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
  • boolean isEmpty()
    -> LinkedList가 비어있는지 알려줌. 비어있으면 true
  • Iterator iterator()
    -> Iterator를 반환
  • int lastIndexOf(Object o)
    -> 지정된 객체의 위치(index)를 반환(끝부터 역순검색)
  • ListIterator listIterator()
    -> ListIterator를 반환
  • ListIterator listIterator(int dex)
    -> 지정된 위치에서부터 시작하는 ListIterator를 반환
  • Object remove(int index)
    -> 지정된 위치(index)의 객체를 LinkedList에서 제거
  • boolean remove(Object o)
    -> 지정된 객체를 LinkedList에서 제거. 성공하면 true, 실패하면 false
  • boolean removeAll(Collection c)
    -> 지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
  • boolean retainAll(Collection c)
    -> 지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
  • Object set(int index, Object element)
    -> 지정된 위치(index)의 객체를 주어진 객체로 바꿈
  • int size()
    -> LinkedList에 저장된 객체의 수 반환
  • List subList(int fromIndex, int toIndex)
    -> LinkedList의 일부를 List로 반환
  • Object[] toArray()
    -> LinkedList에 저장된 객체를 배열로 반환
  • Object[] toArray(Object[] a)
    -> LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환
  • Object element()
    -> LinkedList의 첫 번째 요소 반환
  • boolean offer(Object o)
    -> 지정된 객체(o)를 LinkedList의 끝에 추가. 성공하면 true, 실패하면 false
  • Object peek()
    -> LinkedList의 첫 번째 요소를 반환
  • Object poll()
    -> LinkedList의 첫 번째 요소를 반환. LinkedList에서는 제거됨
  • Object remove()
    -> LinkedList의 첫 번째 요소를 제거
  • void addFirst(Object o)
    -> LinkedList의 맨 앞에 객체(o)를 추가
  • void addLast(Object o)
    -> LinkedList의 맨 끝에 객체(o)를 추가
  • Iterator descendingIterator()
    -> 역순으로 조회하기 위한 DescendingIterator 반환
  • Object getFirst()
    ->LinkedList의 첫 번째 요소 반환
  • Object getLast()
    -> LinkedList의 마지막 요소 반환
  • boolean offerFirst(Object o)
    -> LinkedList의 맨 앞에 객체(o)를 추가. 성공하면 true
  • boolean offerLast(Object o)
    -> LinkedList의 맨 끝에 객체(o)를 추가. 성공하면 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에서 마지막으로 일치하는 객체를 제거

ArrayList와 LinkedList

  • 순차적으로 추가/삭제하는 경우 ---> ArrayList

  • 중간 데이터를 추가/삭제하는 경우 ---> LinkedList

ArrayList와 LinkedList는 상황에 맞게 선택하여 사용하면 된다~

둘의 혼용하는 방법도 있는데,
작업하기 전에 데이터를 작성할 때는 ArrayList를 사용하고
작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있다.

ArrayList al = new ArrayList(1000000);
for(int i=0; i<100000; i++){
	al.add(i+"");
}
LinkedList ll = new LinkedList(al);
for(int i=0; i<1000; i++){
	ll.add(500, "x");
}

컬렉션 프레임웍에 있는 대부분의 컬렉션 클래스들은 이처럼 변환이 가능한 생성자를 제공해서 이걸 이용해서 데이터를 옮기면 된다.

profile
keep going on~

0개의 댓글