연결 리스트 (Linked List)

DataStructure - LinkedList

Posted Mar 26, 2024

18 min read

☻ LinkedList (연결 리스트)
☺︎ LinkedList 특징
☺︎ LinkedList의 종류
☺︎ LinkedList와 ArrayList의 차이
☺︎ LinkedList와 ArrayList 시간 복잡도
☺︎ LinkedList 사용 상황
☺︎ 큐에서 LinkedList의 사용 이유
Java Collection 프레임 워크
추상적 자료형 (ADT)

✏️ 궁금한 것

추상적 자료형
ArrayList, LinkedList, 배열의 차이와 사용 상황
큐에서 LinkedList 사용하는 이유

◼︎ LinkedList (연결 리스트)

개념

노드(객체) 끼리의 주소 포인터를 서로 가리키며, 링크(참조)함으로써 이어지는 구조로, 노드마다 각기 객체 주소를 서로 참조함으로써 연결 형태를 구성한다.
순열(Sequence)라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임
순서가 있다는 점에서 집합과는 구별되며, 일렬로 나열되어 처음과 끝이 각각 하나씩만 있다는 점에서 그래프와도 구별

연결 리스트 내부 동작 방식

연결 리스트는 동적 배열로 크기를 생성하고, 지정할 필요가 없다. 또한, 요소를 삭제하거나 추가하면 자동으로 크기가 자동으로 늘고, 감소한다.

요소는 연속적인 방식으로 저장되지 않는다.

◼︎ LinkedList 특징

이점

1. 동적 크기

크기는 동적으로 늘고, 줄기 때문에 초기에 크기를 할당하지 않아도 된다.

2. 효율적인 삽입과 삭제 연산

삽입 또는 삭제 지점 이후의 모든 요소를 이동하는 대신에, 요소의 링크만 변경하기 때문에 목록 중간에 요소를 삽입하거나 삭제할 수 있다.

단점

1. 성능

개별 요소에 접근할 때, ArrayList보다 성능이 느리다.

원하는 요소에 접근하기 위해, 목록을 순회해야 하는 반면 ArrayList를 사용하면 인덱스를 사용해 원하는 요소에 접근할 수 있다.

2. 메모리 오버헤드

LinkedList는 ArrayList보다 더 많은 메모리를 요구한다. 각 요소에는 이전, 다음 요소에 대한 링크를 위한 추가 메모리가 필요하기 때문이다.

◼︎ LinkedList의 종류

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

요소들이 연속된 메모리 위치에 저장되지 않고, 포인터를 사용하여 각 요소가 다음 요소에만 연결되어 있다.

단점

단방향 연결 리스트는 다음 노드를 가리키는 next 필드만을 갖고 있다.

따라서 현재 요소에서 이전 요소로 접근할 수가 없다. 만약, 저장된 데이터가 1000개라면 999번째 데이터에 접근하기 위해 Node를 999번 순회해야 한다. 따라서, 이를 보완하기 위한 것이 Doubly Linked List이다.

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

양방향 연결 리스트는 이전 노드와 다음 노드를 모두 참조할 수 있다.

  
public class Node { 
    int data;  // 노드에 저장된 데이터 
    Node prev; // 이전 노드 참조
    Node next; // 다음 노드 참조
  
    public Node(int data) 
    { 
        this.data = data; 
        this.prev = null; 
        this.next = null; 
    } 
} 

prev에 이전 노드에 주소를 담아, 역순으로도 검색이 가능하다. 따라서, 양방향 연결 리스트는 단일 연결 리스트보다 각 요소에 대한 접근과 이동이 쉽다.

실제로 Java 컬렉션 프레임 워크의 LinkedList는 Doubly Linked List로 구현되어 있다.

◼︎ LinkedList와 ArrayList의 차이

	ArrayList	LinkedList
컬렉션 구성	동적 배열을 사용하여 요소를 저장	이중 연결 리스트를 사용하여 요소를 저장
데이터 접근 시간	모든 데이터 상수 시간 접근	위치에 따라 이동 시간 발생
삽입 / 삭제 시간	삽입, 삭제 시 데이터 이동이 필요한 경우 추가 시간 발생	삽입, 삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리사이징 필요	공간 부족할 경우, 새로운 배열에 복사하는 추가 시간 발생
데이터 검색	최악의 경우 리스트에 있는 아이템 수 만큼 확인	최악의 경우 리스트에 있는 아이템 수 만큼 확인

◼︎ LinkedList와 ArrayList 시간 복잡도

ArrayList

ArrayList는 내부적으로 데이터를 저장하고 가져오는 데 배열을 사용한다.

배열은 인덱스를 통해 직접 접근이 가능한 자료구조이기 때문에, 특정 위치의 데이터를 가져오거나 설정하는데 걸리는 시간이 일정하다.

따라서 get 및 set 메소드의 시간 복잡도는 O(1)이다.

LinkedList

내부적 배열을 사용해 인덱스로 바로 요소에 접근 가능한 ArrayList와는 달리, LinkedList는 데이터와 이전, 다음 요소에 대한 참조만을 가지고 있다.

따라서 특정 요소를 찾기 위해 최악의 경우 리스트의 처음부터 끝까지 순회해야 하므로, 시간 복잡도는 O(n)이다.

연산	시간 복잡도	설명
접근	O(n)	노드로 x번 이동해야 한다. 마지막 노드에 접근하려면, Head에서 다음 노드로 n-1번 이동해야 한다.
탐색	O(n)	선형 탐색을 하는데, 가장 앞 노드부터 다음 노드를 하나씩 보면서 데이터를 찾아야 한다. 데이터가 Tail 쪽에 있을 경우, 그만큼 탐색 시간은 증가한다.
삽입, 삭제	O(1)	삽입, 삭제할 노드의 주변 Link만 수정하면 된다. 따라서, 삽입, 삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정하다.

◼︎ LinkedList 사용 상황

1. 데이터의 삽입과 삭제가 빈번하게 일어나는 경우

LinkedList는 자료의 삽입, 삭제 연산 시간 복잡도는 주변 노드의 링크만 수정하면 되기에 O(1)의 시간 복잡도를 갖는다. 따라서 상대적으로 삽입, 삭제 속도가 빠르다.

2. 데이터의 크기가 불특정 또는 불규칙한 경우

ArrayList와 같은 동적 배열은 초기에 배열의 크기를 지정해야 하지만, LinkedList는 노드가 동적으로 할당되므로 데이터의 크기가 불특정 또는 불규칙할 때 유용하다.

3. 데이터의 순차적 접근이 아닌, 중간 위치의 삽입과 삭제가 필요한 경우

각 노드가 다른 노드와의 연결 정보를 가지고 있어 중간 위치에서의 데이터 추가 및 삭제가 용이하므로, 데이터의 순차적 접근이 아니라 중간 위치에서의 작업이 필요한 경우에 유용하다.

︎◼︎ 큐에서 LinkedList의 사용 이유

1. 삽입과 삭제의 효율성

큐는 FIFO 자료구조로,데이터 삽입, 삭제 연산이 빈번하게 일어난다. LinkedList는 O(1)의 삽입 삭제 연산 시간 복잡도를 갖기에 효율적으로 인큐, 디큐 연산을 빠르게 처리할 수 있다.

2. 동적 할당

큐는 미리 최대 크기를 예측하기 어렵다. 따라서, 동적으로 노드를 할당하고 해제할 수 있는 LinkedList가 효과적이다.

왜 예측하기 어렵지

최근 코테랑 알고리즘 풀이에 매몰되어 있다보니 들어갈 데이터는 정해져 있는데, 왜 크기 예측이 어려운지 이해가 안 갔다. 단편적인 생각이다.

큐는 비동기 작업, 데이터 버퍼, 캐시 구현 등 다양한 상황에서 사용될 수 있다.

◼︎ Java Collection 프레임 워크

우선, Java에서 컬렉션은 데이터 그룹을 나타내는 인터페이스로, 여러가지 데이터를 담을 수 있는 자료구조의 일종이다.

인터페이스란 어떠한 것이 동작해야 하는지를 결정하는 규칙의 집합인데, 이 인터페이스를 통해 다양한 형태의 컬렉션을 구현할 수 있다.

컬렉션 프레임 워크 내의 List 그리고 LinkedList

리스트는 이 컬렉션 인터페이스를 확장한 것인데, 처음에 ‘확장’ 이라는 말의 의미가 직관적으로 이해가 안 됐다. 더 찾아보니, 기존의 인터페이스에 추가적인 기능을 부여하는 것을 말 한다.

그렇다면 List 인터페이스는 순서가 있는 요소의 집합을 다루는 메소드를 추가로 정의하고 있다.

그럼 Abstract List는 무엇인가?

리스트의 인터페이스를 구현하는 추상 클래스이다.

일부 메소드의 형태만 정의하고, 실제 구현은 하위 클래스에게 맡긴다. 이렇게 하면 상위 클래스에서는 공통적 부분만 정의하고, 세부적 동작 방식은 하위 클래스에서 결정할 수 있다.

즉, 다시 정리하면

Collection이라는 데이터 그룹을 나타내는 인터페이스가 있다.
그리고, List는 이 컬렉션 인터페이스를 확장한 것이다. 순서가 있는 요소의 자료구조를 다루기 위해, 메소드를 추가한 인터페이스이다.
그리고, Abstract List라는 추상 클래스에서 이 List 인터페이스를 구현한다.
그 아래, LinkedList와 ArrayList가 있다.

이렇게 구조적으로 분리하여, 코드의 재사용성을 높이고 확장을 가능하게 하여 유연성을 증가시킨다.

◼︎ 추상적 자료형 (ADT)

개념

자료 자체의 형태와, 그 자료에 관계된 연산들을 수학적으로만 정의한 것
자료 구조가 포함하는 구현 세부사항은 전혀 정의하지 않는 것

예를 들면

자동차를 생각해볼 수 있다.

운전자는 엑셀 페달을 밟으면 차가 전진하고 브레이크를 밟으면 차가 멈춘다는 것을 알고 있다. 그러나 자동차가 어떻게 작동하는지, 엔진이 어떻게 가솔린을 연소시켜 힘을 생성하는지 등의 내부 작동 원리를 알 필요는 없다. 이런 것이 추상적 자료형의 원리다.

즉, 사용자는 데이터가 어떻게 저장되고 조직되는지 알 필요가 없다. 대신, 데이터에 어떤 연산을 수행할 수 있는지(추가,제거,검색)만 알면 된다.

추상적 자료형의 종류

자료형	설명
집합	집합은 서로 관련된 항목의 모음
리스트	리스트는 순서가 있는 데이터의 모음
스택	스택은 후입선출(LIFO: Last In, First Out) 방식으로 데이터를 저장하고 접근하는 자료형
큐	큐는 선입선출(FIFO: First In, First Out) 방식으로 데이터를 저장하고 접근하는 자료형
트리	트리는 계층적으로 데이터를 저장하는 자료형
그래프	그래프는 노드와 그 노드를 연결하는 간선으로 이루어진 자료형
연관 배열	연관 배열은 키와 값을 쌍으로 저장하는 자료형

위 자료형들은 추상적 자료형이라고 불린다.

이유는

각각이 데이터의 저장 방식이나 내부 구조보다는, 데이터에 적용할 수 있는 연산들을 정의하고 있기 때문이다.

예를 들어, 리스트라는 추상적 자료형은 데이터를 순차적으로 저장한다는 개념과 데이터를 추가, 검색, 제거하는 연산을 정의하지만, 이 리스트가 배열로 구현 되었는지, 연결 리스트로 구현 되었는지에 대한 정보는 제공하지 않는다.

이렇게 구현 세부사항을 사용자로부터 숨기는 것이 추상화의 원리이다.

왜 숨기는 것인가?

사용자가 필요 이상의 복잡한 내부 구조나 원리를 알 필요 없이, 해당 자료형이 제공하는 기능만을 이해하고 사용할 수 있도록 하기 위해서라고 한다.

CS, DataStructure

DataStructure 자료구조

This post is licensed under CC BY 4.0 by the author.