반응형

* LinkedList (연결리스트)

연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다.

연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인 헤드(Head)로 부터 노드에 다음 노드를 가리키는 포인터를 사용해 리스트를 순회할 수 있게 됩니다.

<List(연결리스트)>

위와 같은 연결리스트를 Singly Linked List라고 합니다.

Singly Linked List의 각 노드에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 되고, 환형 큐(Circular Queue)와 같이 연결리스트의 마지막 노드인 테일(Tail)과 헤드를 이으면 Circular Linked List가 됩니다.
이는 문제의 상황에 따라 구현하여 사용하시면 됩니다.

<Doubly Linked List>

각 노드는 저장할 값과 자신의 앞, 뒤 노드를 가리키는 포인터를 가짐

<Circular Linked List>

테일의 포인터는 헤드를 가리킴

두 자료구조의 장단점을 나열해보자면, 배열은 인덱스로 인한 무작위 접근이 가능하고, 리스트에 비해 저장공간을 적게 필요로 하지만, 리스트에 비해 자료의 삽입, 삭제가 비효율 적인 부분이 있습니다. 순서를 유지하면서 자료를 삽입 / 삭제하기 위해서는 최악의 경우 모든 데이터를 옮겨주어야 하기 때문입니다.

리스트는 무작위 접근이 불가능하므로 무조건 순차적으로 탐색해야 하며, 노드에 저장할 값과 포인터를 포함하고 있기 때문에 똑같은 크기의 배열에 비해 저장공간을 많이 차지하게 되지만, 자료의 삽입과 삭제가 새로운 노드를 만들어 포인터로 이어주기만 하면 되기 때문에 간편하고 유연하게 동작합니다.

List(연결리스트)동적배열
IndexingO(N)O(1)
Insert / Delete at beginningO(1)O(N)
Insert / Delete at endO(1) when last element is known;
O(N) when last element is unknown		O(1)
Insert / Delete in middlesearch time + O(1)O(N)



* 출처 & 참고 링크

Samsung CodeGround

ArrayList vs LinkedList


반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
[Data Structure] Queue (큐)  (0) 2019.01.17
[Data Structure] ArrayList vs LinkedList  (0) 2018.12.27
반응형

* ArrayList vs LinkedList

ArrayList와 LinktedList 둘다 모두 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체이다.

하지만 내부적으로 작동하는 방식은 다르다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList<String> alist = new ArrayList<>();
        alist.add(0,"First");           //O(1)
        alist.add("Second");            //O(1)
        alist.add(2, "Third");          //O(1)
        alist.remove(1);                //O(n)
 
        alist.get(1);                   //O(1)
 
        LinkedList<String> nlist = new LinkedList<>();
        nlist.addFirst("First");        //O(1)
        nlist.add("Second");            //O(1)
        nlist.addLast("Third");         //O(1)
        nlist.pollFirst();              //O(1)
        nlist.pollLast();               //O(1)
 
        nlist.get(0);                   //O(n)
    }
}
 
cs

알고리즘 문제를 풀면서 가장 중요한 ArrayList와 LinkedList의 차이점은 시간복잡도의 차이라고 볼 수 있다.

ArrayList는 동적으로 Array를 생성한다고 생각하면 배열과 비슷한 점이 많다.

ArrayList는 remove 시에 O(n)의 시간복잡도를 가진다.

i번째 배열을 지우고 최대 n만큼 앞으로 이동해야 하기 때문이다.

삽입 또한 맨 뒤에삽입과 중간삽입으로 나눌 수 있는데, 중간에 삽입하는 경우 O(n), 맨 뒤에 삽입하는 경우 O(1)의 시간복잡도를 가진다.

하지만 get 메소드는 해당 index를 바로 가져오기 때문에 O(1)의 시간복잡도를 가진다.


이에 비해, LinkedList는 Node를 사용하기 때문에 add, poll 시에 O(1)의 시간복잡도를 가진다.

하지만 get 메소드 사용시에 앞에서부터 찾기 때문에 O(n)의 시간복잡도를 가진다.

이를 정리하면 다음과 같다.

 

 ArrayList

 LinkedList

삽입

 add  >> O(1) or O(n)

add, addFirst, addLast >> O(1)

삭제 

 remove >> O(n)

poll, pollFirst, pollLast >> O(1)

get 

 get(index) >> O(1)

get(index) >> O(n) 

반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
[Data Structure] Queue (큐)  (0) 2019.01.17
[Data Structure] LinkedList (연결리스트)  (0) 2019.01.17

티스토리툴바