3. 1. Linked List - 개념, 경계조건, addFirst, addLast (자바로 구현하고 배우는 자료구조)

레퍼런스는 네이버 edwith - 자바로 구현하고 배우는 자료구조 입니다.

연결 리스트란?

head가 있고,
head.next -> Node B
head.data = 10;

head.next.next -> Node C
head.next.data = 15;

head.next.next.next -> null
head.next.next = 30;

data 또한 Pointer이다. 
(data에 객체도 들어 갈수 있다는 것을 말하고 싶으신듯)
이렇게 포인터로 연결 되어 있다.

---

노드와 크기

• 링트 리스트 만들기

  • 이너 클래스를 이용하면 외부에서 접근이 불가능하다.
  • 이렇게 해야 만들어 놓은 링트 리스트를 외부에서 접근하지 않아 보호가 된다.
  • 노드를 건들려면 public class LinkedList 내부에서만 접근이 가능하다. LinkedList.method(); 만들어서 접근해야한다는걸 설명하고 싶으신듯

  

public class LinkedList<E> implements List<E> {

    class Node<E> {

        E data;
        Node<E> next;

        public Node(E obj) {
            data = ojb;
            next = null;
        }
    }

    private Node<E> head;
    private int currentSize;

    public LinkedList () {
        head = null;
        currentSize = 0;
    }
    @override
...
}

• currentSize를 만들어 두는 이유는 head 부터 next, next, next해서 세는거 자체가 세타(n)의 알고리즘이기 때문에, 변수 하나를 둬서 현재 위치를 적어 두는거다.

---

경계 조건 (Boundary Conditions)

• Data Structure 설계할 때, 메서드 구현할 때 꼭 고려 해야 하는 5가지 Boundary Conditions가 있다.
  1. 비어있을 때
  2. 원소가 하나 있을 때
  3. Add / Remove 시작 부분에
  4. Add / Remove 끝 부분에
  5. 중간 부분 처리할 때

---

addFirst

public void addFirst(E obj) {
        Node<E> node = new Node<>(obj);
        node.next = head;
        head = node;
        currentSize++;
    }

• 컨셉은 간단하지만 [node.next](<http://node.next>) = head' 이런식으로 하다 보니 계속 헷갈린다. PS로 문제 풀어보면서 익숙해지는게 답일것 같다. 우선은 강의를 계속 들어보자.
• addFirst 할 때는 순서가 중요하다. 만약 [node.next](<http://node.next>) = head;보다 head = node; 를 먼저 해버리면, head가 기존에 가지고 있던 A노드의 주소값을 잃어버리게 되고, 그렇게 연결을 잃으면 Garbage Collector가 메모리를 정리해 버린다. 주의 해야 한다.

---

addLast 메소드

public void addLast(E obj) {
        Node<E> node = new Node<>(obj);
        Node<E> tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = head;
                currentSize++;
    }

• Boundary condition : When the Structure is empty

// head == null 일때 처리
if (head == null) {
    head = node;
    currentSize++;
}

• 마지막 node를 찾을때마다 O(n)을 거쳐야 찾을수 있게된다.
• 그래서 tail 포인터를 만들어 주어 마지막 포인터를 찾는 시간을 O(1)로 하기로했다.
• 코드는 좀더 복잡해지지만 훨씬 좋은 방법이 된다.

private Node<E> tail; //클래스에 멤버 추가

// AddFirst에 head == null일때 addFirst 하면 tail = node; 추가
public void addFirst(E obj) {
        Node<E> node = new Node<>(obj);
        if (head == null) { 
            tail = node;
        }
        node.next = head;
        head = node;
        currentSize++;
    }

// addLast는 tail 덕에 while문 없어져서 좋다.
public void addLast(E obj) {
        Node<E> node = new Node<>(obj);
        if (head == null) {
            head = node;
            tail = node;
            currentSize++;
        }
        tail.next = node;
        currentSize++;
    }

---