[자료구조] - 리스트

1. 리스트

1.1 리스트란?

연결 리스트, 링크드 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄(선형)로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. (* wikipedia)

1.2. 리스트의 종류

1.2.1. 단일 연결리스트

 

각 노드가 앞에서 뒤로의 연결만을 가진 연결리스트

단일 연결이기에 각 노드의 포인터에는 후행 노드의 주소값이 저장되어 있다.

-> 뒤에서 앞으로의 접근은 불가.

public class Node<T> {
    Node<T> next = null;
    T data = null;
}

public class SinglyLinkedList<T> {
    Node<T> head = null;
    int length = 0;

• 이미 리스트가 구현되어 있으므로 구현법을 아는 것은 당장은 중요하지 않음
• 그러나 실력이 올라간다면 리스트의 개념을 보고 구현 해보길 추천 그리고 구현되어있는 API와의 비교

==장점==

1. 공간을 미리 할당하지 않음
   -> 배열의 경우 인덱스 생성 시 미리 공간을 할당
   -> 리스트의 경우 add remove 시에 따라 가변적
2. 삽입/삭제가 빠르다.
   -> 배열은 중간 idx가 삭제된 경우 다른 인덱스의 재배치가 필요

==단점==

1. 접근 연산에 불리하다.
   -> 배열은 idx를 접근하여 O(1)
   -> 리스트는 위치를 찾아야해서 O(N)

1.2.2. 이중 연결리스트

 

단일과 다르게 노드와 노드가 서로 연결

따라서 양방향 탐색이 가능해짐

public class Node<T> {
    Node<T> next = null;
    NodE<T> pre = null;
    T data = null;
}

==장점 ==

1. 단방향의 장점 + 단점을 개선
   -> 양방향이므로 탐색이 O(n)에서 최대 반으로 줄어듦
   ==단점==
2. 메모리를 더 많이 차지 pre 변수가 생겼기 떄문

그럼에도 불구하고 많은 구현이 양방향 연결리스트이다. 이점이 더 많기 때문

 

1.2.3. 원형 연결리스트

간단히 양방향 연결리스트에서 tail 의 next를 head 에 연결

 

head 의 pre 는 tail 에 연결

 

시작점을 알 수 없기에 dummy node로 시작점을 안내

2. 리스트가 중요한 이유

2.1. 배열만큼 넓은 활용도

우선 웹개발을 한다면 기본적으로 JPA 연관관계 매핑 시 ArrayList<> 를 많이 활용하므로 익숙

 

그 외에도 다양한 알고리즘의 구현체가 ArrayList<> 인 경우가 많음

e.g.)

• 팰린드롬 수 (Palindrom)
  앞에서 읽으나 뒤에서 읽으나 같은 문장 및 단어 'ABA'
  (https://www.acmicpc.net/problem/1259)
• 문자열 뒤집기
  • 반복문과 조건문, 대입개념 활용
  • 리스트 메서드 활용 - reverse()
    (https://www.acmicpc.net/problem/19597)

그 외에도 너무 많아가지고..