자료구조 - Linked List

LinkedList

ArrayList처럼 인덱스로 접근하여 조회/ 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다.

ArrayList는 배열을 이용하여 메서드로 조작을 하지만, Linked List는 노드(객체)끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다.

 

class Node {
	Node next; // 다음 노드 주소를 저장하는 필드
    int data; // 데이터 저장 필드
}

 

 

LinkedList 종류

단방향 연결 리스트(singly linked list)

 

다음 노드를 가리키기 위한 포인터필드 next만 가지고 있는 링크드 리스트를 singly linked list라고 한다.

단일 연결 리스트는 현재 요소에서 이전 요소로 접근해야 할때 매우 부적합한 특징이 있다.

 

 

양방향 연결 리스트(doubly linked list)

class Node {
	Node next; // 다음 노드 주소 저장
    Node prev; // 이전 노드 주소 저장
    int data; // 데이터를 저장
}

 

기존의 단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 필드 prev가 추가된 형태를 doubly linked list라고 부른다.

singly linked list는 이동 방향이 단방향이기 때문에, 이를 보완하여 역순으로 검색이 가능하도록 한것이다.

실제 Java의 LinkedList는 doubly linked list로 구현되어 있다.

 

양방향 원형 연결 리스트(doubly circular linked list)

첫 번째 노드와 마지막 노드를 연결시켜, 마치 원형 리스트처럼 만들었다.

 

LinkedList vs ArrayList

	ArrayList	LinkedList
컬렉션 구성	배열 사용	노드 연결
데이터 접근 시간	상수 시간 접근	위치에 따라 이동시간 추가
삽입 / 삭제 시간	삽입 / 삭제 자체는 상수 시간
라사이징 필요	공간 부족시 새로운 배열에 복사하는 추가시간
데이터 검색	리스트에 있는 아이템 수 만큼 검색
CPU Cache	캐시 이점을 활용

 

 

LinkedList 사용법

LinkedList는 List 자료구조 외에도 Stack이나 Queue 자료구조로서도  이용이 가능하다.

- 내부 메서드 갯수가 컬렉션 중에 가장 많다.

 

LinkedList 객체 생성

import java.util.LinkedList;

 

생성자	설명
LinkedList()	LinkedList 객체를 생성
LinkedList(Collection c)	주어진 컬렉션을 포함하는 LinkedList 객체를 생성

 

// 타입 설정 
LinkedList<Integer> list = new LinkedList<>();

// 생성시 초기값 설정
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));

 

ArrayList처럼 초기 값을 미리 지정하는 기능은 제공되지 않는다. 내부 데이터 집합 구조가 배열처럼 미리 공간을 할당하고 사용하는 방식이 아닌, 데이터가 추가될 때 마다 노드(객체)들이 생성되어 동적으로 추가되는 방식이다.

 

LinkedList 요소 추가 / 삽입

LinkedList에는 4종류의 add 메서드가 존재한다. 

기본적인 add() 메서드는 addLast()와 동일하다.

메서드	설명
void addFirst(Object obj)	LinkedList의 맨 앞에 객체(obj)를 추가
void addLast(Object obj)	LinkedList의 맨 뒤에 객체(obj)를 추가
boolean add(Object obj)	LinkedList의 마지막에 객체를 추가 (성공시 true)
void add(int index, Object element)	지정된 위치(index)에 객체를 저장
void addAll(Collection c)	주어진 컬렉션의 모든 객체를 저장(마지막에 추가)
void addAll(int index, Collection c)	지정한 위치부터 주어진 컬렉션의 데이터를 저장

 

LinkedList의 가장 큰 특징은, ArrayList와 다르게 중간에 데이터가 추가되거나 중간에 있는 데이터가 삭제되어도 앞으로 땡기거나 뒤로 미는 동작이 없다는 점이다. 추가되거나 삭제될 노드 위치의 바로 앞뒤쪽에 있는 노드의 참조를 변경하기만 하면 된다.

LinkedList는 할당이 고정된 크기 개념이 아니므로 메모리가 충분하는 한 무한정으로 요소를 저장  할 수 있다.

 

가장 앞에 추가

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

list.addFirst("new");

 

 

가장 뒤에 추가

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

// 가장 뒤에 데이터 추가
list.addLast("new");

 

중간에 추가

LinkedList<Integer> list = new LinkedList<>(Arrays.asList("A","B","C"));

// index 1 중간 위치에 데이터 추가
list.add(1,"new");

 

addFirst(), addLast()는 요소를 첫번째, 마지막에 추가하는 것이므로 O(1)이 걸린다.
중간 삽입일 경우 중간에 삽입할 위치까지의 탐색을 필요하기 때문에 O(N)의 시간이 걸린다.

 

LinkedList 요소 삭제

remove 메서드에서 removeFirst(), removeLast()는 O(1), 그 외에는 타색 시간이 필요하므로 O(N)이 걸린다.

값을 전부 제거하려면 clear() 메소드를 사용하면 된다.

메서드	설명
Object removeFirst()	첫번째 노드를 제거
Object removeLast()	마지막 노드를 제거
Object remove()	LinkedList의 첫 번째 요소를 제거
Objeckt remove(int index)	지정된 위치(index)에 객체를 제거
boolean remove(Object obj)	지정된 객체를 제거(성공하면 true)
boolean removeAll(Collection c)	지정한 컬렉션에 저장된 것과 동일한 노드들을 LinkedList에서 제거
boolean retainAll(Collection c)	LinkedList에 저장된 객체 중에서 주어진 컬렉션과 공통된 것들만 남기고 제거한다.
void clear()	LinkedList를 완전히 비운다.

 

첫번째 값 제거

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));
list.removeFirst();

 

마지막 데이터 제거

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));
list.removeLast();

 

중간 위치 제거

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));
list.remove(1);

 

모든 값 제거

list.clear();

 

 

LinkedList 검색

리스트에 요소 존재 여부를 검색하는 방법은 요소 자체가 리스트에 있는지 검사하는 contains(), 인덱스 위치도 반환해주는 indexOf()

메서드	설명
int size()	LinkedList에 저장된 객체의 개수를 반환한다.
boolean isEmpty()	LinkedList가 비어있는지 확인한다.
boolean contains(Object obj)	지정된 객체(obj)가 LinkedList에 포함되어 있는지 확인한다.
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되었는지 알려준다.
int indexOf(Object obj)	지정된 객체(obj)가 저장된 위치를 찾아 반환한다.
int lastIndexOf(Object obj)	지정된 객체(obj)가 저장된 위치를 뒤에서부터 역방향으로 찾아 반환한다.

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 해당 값을 가지고 있는 요소 위치를 반환 (앞에서 부터 검색) 
list1.indexOf("B"); // 1

// 해당 값을 가지고 있는 요소 위치를 반환 (뒤에서 부터 검색) 
list1.lastIndexOf("D"); // -1 : 찾고자 하는 값이 없으면

LinkedList list1 = new LinkedList();
list1.add("1");
list1.add("2");

// list1안에 "1" 값이 있는지 확인
list1.contains("1"); // true


LinkedList list2 = new LinkedList();
list2.add("1");
list2.add("2");
 
// list1에 list2의 모든 노드가 포함되어 있는지 확인
list1.containsAll(list2); // true

 

LinkedList 요소 얻기

메서드	설명
Object get(int index)	지정된 위치(index)에 저장된 객체를 반환한다.
List subList(int fromIndex, int toIndex)	fromIndex부터 toIndex 사이에 저장된 객체를 List로 반환한다.

 

list.get(0); // 0번째 index 요소의 값 출력

LinkedList 요소 변경

메서드	설명
Object set(int index, Object obj)	지정한 위치(index)의 객체를 주어진 객체로 바꾼다.

LinkedList<String> list = new LinkedList<>();
list1.add("10");
list1.add("20");
list1.add("30");
 
list1.set(1, "A"); // index 1번의 데이터를 문자열 "A"로 변경한다.
System.out.println(list1); // // [10, A, 30]

 

LinkedList 배열 변환

메서드	설명
Object[] toArray()	LinkedLsit에 저장된 모든 객체들을 객체배열로 반환한다.
Object[] toArray(Object[] objArr)	LinkedList에 저장된 모든 객체들을 객체배열 objArr에 담아 반환한다.

 

LinkedList<Number> list1 = new LinkedList<>();
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(4);
 
Number[] arr = (Number[]) list1.toArray();
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4]

LinkedList<Number> list1 = new LinkedList<>();
list1.add(1);
list1.add(2);

Object[] tmp = {0, 1, 2, 3, 4, 5}; // 통째로 추가할 배열

Number[] arr = (Number[]) list1.toArray(tmp);
System.out.println(Arrays.toString(arr)); // [1, 2, null, 3, 4, 5]

 

LinkedList 동기화 처리

멀티 쓰레드 환경에서 동시에 컬렉션에 접근해 문제가 발생하는 것을 방지하기 위해 동기화 처리된 리스트를 반환받아 사용할 수 있다.

List<String> l1 = Collections.synchronizedList(new ArrayList<>());
List<String> l2 = Collections.synchronizedList(new LinkedList<>());