Linked List (연결 리스트)

Linked List

리스트 자료구조는 중복 저장을 허용하며 데이터를 나란히 저장한다.

자바에는 리스트 자료구조를 정의해놓은 List컬렉션이 있다. (인터페이스)

• 객체를 인덱스로 관리하여 객체를 삽입하면 인덱스가 자동으로 부여된다.
• 그래서 인덱스로 객체에 검색, 삭제가 가능하다.
• 객체를 직접 저장하고 있지 않고 객체의 주소를 가지고 있다.
  • null도 저장이 가능하다. (아무것도 참조하지 않는 상태)
• 구현체로 ArrayList, LinkedList, Vector 등이 있다.

LinkedList(연결 리스트)는 List 인터페이스의 구현체로 메모리의 동적할당을 기반으로 구현된 리스트다.
LinkedList의 모든 노드는 인접 노드를 참조해서 체인처럼 관리한다.

https://www.callicoder.com/java-linkedlist/

노드를 리스트의 중간에 삽입하여도 인접한 노드들의 링크만 변경하면 되고, 다른 노드들에는 영향이 없다.
따라서 빈번한 객체 삽입/삭제가 일어날때 적합하다.

ArrayList의 경우는 중간에 노드를 삽입하려면 해당 인덱스 뒤의 노드들을 모두 1씩 밀어야한다. 그래서 비용이 커진다.
그러나 맨 마지막에 객체를 추가하거나 인덱스 검색을 하는 경우엔 ArrayList의 성능이 더 좋다.

자바 메소드

객체 추가
- boolean add(E e) : 객체를 맨 끝에 추가한다. 성공적으로 추가되면 true를 리턴한다.
- void add(int index, E element) : 주어진 인덱스에 객체 추가한다.
- E set(int index, E element) : 주어진 인덱스에 저장된 객체를 주어진 객체로 바꾼다. 바꾸기 전 원래 객체를 리턴한다.
객체 검색
- boolean contains(Object o) : 주어진 객체가 저장되어 있는지 여부를 확인한다. 저장되있으면 true를 리턴한다.
- E get(int index) : 주어진 인덱스에 저장된 객체를 리턴한다.
- boolean isEmpty() : 컬렉션이 비어있으면 true를 리턴한다.
- int size() : 리스트의 크기를 리턴한다.
객체 삭제
- void clear() : 저장된 모든 객체를 삭제한다.
- E remove(int index) : 주어진 인덱스에 저장된 객체를 삭제하고 삭제한 객체를 리턴한다.
- boolean remove(Object o) : 주어진 객체를 찾아서 삭제한다.

자바 LinkedList 구현 (정수 저장 자료구조 LinkedNode)

테스트코드 포함 깃허브 링크

package com.example.LinkedList;

import java.util.Objects;

public class ListNode {

    protected ListNode next;
    protected int data;

    public ListNode() {
    }

    public ListNode(int data) {
        this.data = data;
    }

    // before = 대상 인덱스를 가리키고 있는 노드
    static public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        validatePositionInput(position);

        ListNode before = head;
        while (position > 0) {
            validateNextNode(before.next);
            before = before.next;
            position--;
        }

        if (!Objects.isNull(before.next)) { // 삽입하려는 인덱스가 비어있지 않은 경우
            nodeToAdd.next = before.next;
        }
        before.next = nodeToAdd;

        return nodeToAdd;
    }

    public static ListNode remove(ListNode head, int positionToRemove) {
        validatePositionInput(positionToRemove);

        ListNode before = head;
        while (positionToRemove > 0) {
            validateNextNode(before.next);
            before = before.next;
            positionToRemove--;
        }

        ListNode removed =  before.next;
        before.next = before.next.next;

        return removed;
    }

    static private void validatePositionInput(int position) {
        if (position < 0) {
            throw new IllegalArgumentException("포지션은 0이상 이어야 합니다.");
        }
    }

    static private void validateNextNode(ListNode nextNode) {
        if (Objects.isNull(nextNode)) {
            throw new NullPointerException("포지션이 리스트의 길이를 초과합니다.");
        }
    }

    public static boolean contains(ListNode head, ListNode nodeToCheck) {

        ListNode before = head;
        while (!Objects.isNull(before.next)) {
            if (before.next.equals(nodeToCheck)) {
                return true;
            }
            before = before.next;
        }

        return false;
    }
}