List

본 문서는 2022년 1월 1일 에 작성되었습니다.
추가로 2022년 1월 4일 에 Java 코드 파트를 추가하였습니다.

Linked List 에 대해서 설명하기 위해서 단게적으로 다음의 내용을 짚어볼 생각입니다.

1. List 란?
2. Array List 란?
3. Linked List 란?

이후, Linked List 의 세부 프로시저에 대해서 알아보겠습니다.

---

알고리즘학

List, ArrayList, Linked 를 알고리즘학 관점에서 설명하는 내용입니다.
참고 도서는 Introduce to Algorithm 이며, 실제 코드는 아래를 참고해주세요.

List 란?

List 는 Java(jdk 1.8) 에 있는 Interface 인 List 를 의미합니다.
나아가, 알고리즘 학문에서의 선형적 순서를 가지는 데이터 집합 을 의미하기도 합니다.

공통점은 Index 를 이용하여 선형적인 순서 를 구현하였다는 것 정도 입니다.
따라서 Index 를 가지는 일반적인 배열과 목적, 기능상으로 동일하다고 봐도 무방합니다.

---

Array List 란?

Array List 는 Java(jdk 1.8) 에 있는 Collection Framework 의 Class 중 하나를 의미하며, List 를 상속받아서 사용되고 있습니다.

따라서,
Array List 또한 선형적 순서를 가지고 있으며 이를 Index 를 통해서 구현 하였습니다.

특정 언어군에서는 Array List 라는 겅시 존재하지 않을 수도 있습니다.
Javascript 의 배열은 길이가 늘어날 수 있기 때문에, 굳이 필요없지 않나 싶다.

---

Linked List 란?

Linked List 는 Java(jdk 1.8) 에 있는 Collecton Framework 의 Class 중 하나를 의미하고 있습니다. 동시에 일반적인 알고리즘학 에서의 Linked List 를 의미하기도 합니다.

배열, List, Array List 등이 Index 로 선형적인 순서 를 구현하지만
Linked List 는 Node 로 선형적인 순서 를 구현합니다.

Node 는 화살표라고 이해하면 십습니다.
내 다음 혹은 이전으로 가는 화살표를 내가 기록하고 있는 개념입니다.

이러한 Node 는 다음과 같익 구현할 수 있습니다.

1. Pointer 를 이용한 구현 (C 언어군 혹은 Pointer 를 지원하는 언어군)
2. Object 를 이용한 구현 (Node Class 를 만들엇 이를 사용하기)

Java(jdk 1.8) 의 Collection Framework 의 Linked List 는 2번 방법으로 구현되어 있습니다.

이러한 Linked List 의 주요 프로시저는 다음과 같습니다.

1. LIST SEARCH
2. LIST INSERT
3. LIST DELETE

# List Search

L 은 Linked List 형태의 배열(집합) 을 의미합니다.
k 는 검색 대상을 의미합니다.

최악의 경우 모든 대상을 검색해야 하므로 O(n) 의 수행시간이 걸린다.

LIST SEARCH (L, k)

   x = L.head
   while x!=NIL and x.key!=k
      x = N.next
   return x;

# List Insert

L 은 Linked List 형태의 배열(집합) 을 의미합니다.
x 는 검색 대상을 의미합니다.

1개의 추가를 위해서 1개의 작업만 실행하므로 O(1) 이다.

LIST INSERT (L, x)

   x.next = x.head
   if L.head != NIL
      L.head.prev = x
   
   L.head = x
   x.prev = NIL

# List Delete

L 은 Linked List 형태의 배열(집합) 을 의미합니다.
x 는 검색 대상을 의미합니다.

삭제는 Insert 와 같이 O(1) 이지만,
삭제할 대상을 찾아야 하기 때문에 LIST SEARCH 를 실행하고
결과적으로 O(n) 의 수행시간이 걸린다.

LIST DELETE (L, x)

   if x.prev != NIL
      x.prev = x.next
   else
      L.head = x.next
   
   if x.next != NIL
      x.next.prev = x.prev

---

경계 원소가 있는 Linked List

알고리즘을 공부하다보면 경계 원소 라는 개념이 있다.

경계원소는 한계 조건을 간단하게 해주는 더미 객체이다.
이를 테면, User(Class) 가 담겨있는 Object 배열에 마지막 공간에 null 을 넣어둔다면 이 것이 경계원소로써 작용할 것이다. 이를 통해 우리는 "아 배열의 마지막 공간에 도착했구나" 라고 알 수 있다.

그렇다면, Linked List 에서의 경계 원소는 어떤 것일까?
바로 key 값은 NIL(null) 이며, Node 만 가지고 있는 것들이다.

그렇다면 구체적으로 얼마만큼의 이점 을 누릴 수 있을까?
Linked List에 경계원소를 넣으면 다음 만큼의 이점이 있다.

1. 프로시저가 간결해진다.
2. List Insert 와 List Delete 프로시저의 수행시간이 O(1) 만큼 줄어든다.

그러나!!!
효율적으로 투입된 경계원소는 반복 구문의 효율성을 증대시켜 n, n^2 등의 계소를 감소시킬 수 있다.

*단!!!
크기가 작은 List 가 많이 존재하는 경우에는 메모리 낭비가 심해질 수 있다.

다음은 경계원소를 사용한 경우의 프로시저이다.

# List Search

LIST SEARCH (L, k)

   x = L.nil.next
   while x!=L.nil and x.key!=k
      x = x.next
   return x

# List Insert

LIST INSERT (L, x)

   x.next = L.nil.next
   L.nil.next.prev = x
   L.nil.next = x
   x.prev = L.nil

# List Delete

   x.prev.next = x.next
   x.next.prev = x.prev

---

Java 코드

List, ArrayList, LinkedList 를 Java(jdk 1.8~) Collection Framework 관점에서 설명
하는 내용입니다.
참조 내용과 깃허브 저장소는 다음과 같습니다.

1. java.util.*(Collection Framework)
2. 자바 [Java] - Collection Framework Series (저자 : Stranger's Lab)
3. 깃허브 [GitHub] - 22 algorithm repository (저자 : unchaperted)

List

List Inerface - Github Repository

List 는 인터페이스입니다.

인터페이스는 추상 메서드 만을 가지고 있으며,
이 인터페이스를 상속하는 클래스들에게 추상 메서드를 구현할 책임을 강제합니다.

ArrayList

ArrayList Class - Github Repository

ArrayList 는 클래스입니다.

ArrayLIst 는 List 인터페이스를 상속받고 있습니다.
ArrayLIst 는 List 인터페이스의 구현체입니다.

본 예제에서
ArrayList 는 Cloneable 인터페이스를 상속받고 있습니다.
자세한 내용은 Java - Collection Framework 를 참고해주세요.

LinkedList

Node Class - Github Repository
SingleLinkedLIst Class - Github Repository
DoublyLinkedList Class- Github Repository

LinkedList 는 클래스입니다.

LinkedList 는 List 인터페이스를 상속받고 있습니다.
LinkedList 는 List 인터페이스의 구현체입니다.

본 예제에서
Linked List 는 Cloneable 인터페이스를 상속받고 있습니다.
자세한 내용은 Java - Collection Framework 를 참고해주세요.

또한 Linked List 를 구현하기 위하여 Node 클래스를 구현하였습니다.
더하여 방향성에 따라서 Single/Doubly Linked List 를 구현하였습니다.