Singly Linked List

• Linked List
• Node class
• Singly Linked List class
• add Method
• get Method
• remove Method
• insert Method
• 전체 소스 코드

• Linked List

Linked List에 대해 잘 모르시는 분들은 다음 글을 읽고 오시면 이해가 편하실 겁니다.

https://sw-log.tistory.com/41

Linked List

• Node class

class Node<T> {
  T data;
  Node<T> next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

 

- 제네릭을 활용하여 사용자가 임의로 데이터타입을 결정할 수 있게 했습니다.

 

- 생성 단계에선 포인터가 어떤 노드를 가리키게 될지 알 수 없기 때문에 null로 설정했습니다.

• Singly Linked List class

public class SinglyLinkedList<T> {

  private Node<T> head;

  public int size() {
    if (head == null) return 0;
    else {
      Node<T> cursor = head;
      int count = 1;
      while (cursor.next != null) {
        cursor = cursor.next;
        count++;
      }
      return count;
    }
  }

  private void checkIndex(int index) {
    if (index < 0 || index >= size()) throw new IndexOutOfBoundsException();
  }

  private Node<T> getNode(int index) {
    Node<T> cursor = head;
    int count = 1;
    while (count <= index) {
      cursor = cursor.next;
      count++;
    }
    return cursor;
  }
}

 

- Node<T> head :

Linked List의 시작점을 가리키는 헤드 포인터입니다.

 

- size() :

Linked List의 크기를 반환하는 메서드입니다.

 

- checkIndex(int index) :

매개변수로 받은 index가 유효한 값인지 확인하고 유효하지 않다면 IndexOutOfBoundsException을 발생시킵니다.

 

- getNode(int index) :

매개변수로 받은 index에 위치한 노드를 찾습니다.

• add Method

public void add(T data) {
  Node<T> newNode = new Node<>(data);

  if (head == null) head = newNode;
  else {
    Node<T> lastNode = getNode(size() - 1);
    lastNode.next = newNode;
  }
}

 

- 새로운 노드를 생성합니다.

 

- 헤드 포인터가 null이라면 새로 생성한 노드를 바라보게 합니다.

 

- 첫 번째 노드가 존재한다면 마지막 노드를 찾고 마지막 노드가 새로 생성한 노드를 바라보게 합니다.

• get Method

public T get(int index) {
  checkIndex(index);
  return getNode(index).data;
}

 

- checkIndex()를 통해 index가 유효한지 판단합니다.

 

- getNode()를 통해 매개변수로 받은 index 위치에 있는 노드를 찾고 해당 노드의 데이터를 반환합니다.

• remove Method

public void remove(int index) {
  checkIndex(index);
  if (index == 0) head = head.next;
  else {
    Node<T> prevNode = getNode(index - 1);
    prevNode.next = prevNode.next.next;
  }
}

 

- checkIndex()를 통해 index가 유효한지 판단합니다.

 

- 첫 번째 노드를 삭제한다면 헤드 포인터가 두 번째 노드를 바라보게 합니다.

 

- 그 외의 경우에는 삭제하려는 노드의 타겟 노드의 이전 노드를 찾고, 이전 노드가 이전 노드의 두 번째 다음 노드를 바라보게 합니다.

즉, 이전 노드가 타겟 노드의 다음 노드를 바라보게 하여 더 이상 타겟 노드를 바라보는 노드가 없게 합니다.

 

- Java의 GC가 타겟 노드를 메모리에서 자동으로 삭제하기 때문에 개발자가 이를 신경 쓸 필요는 없습니다.

• insert Method

public void insert(int index, T data) {
  checkIndex(index);
  Node<T> newNode = new Node<>(data);
  if (index == 0) {
    newNode.next = head;
    head = newNode;
  } else {
    Node<T> prevNode = getNode(index - 1);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
  }
}

 

- checkIndex()를 통해 index가 유효한지 판단합니다.

 

- 첫 번째 위치에 추가한다면 새로 생성한 노드가 헤드 포인터가 바라보는 노드를 바라보게 하고, 헤드 포인터는 새로 생성한 노드를 바라보게 합니다.

 

- 그 외의 경우에는 이전 노드를 찾고 이전 노드가 바라보는 노드를 새로 생성한 노드가 바라보게 하고, 이전 노드는 새로 생성한 노드를 바라보게 합니다.

• 전체 소스 코드

public class SinglyLinkedList<T> {

  private Node<T> head;

  public int size() {
    if (head == null) return 0;
    else {
      Node<T> cursor = head;
      int count = 1;
      while (cursor.next != null) {
        cursor = cursor.next;
        count++;
      }
      return count;
    }
  }

  private void checkIndex(int index) {
    if (index < 0 || index >= size()) throw new IndexOutOfBoundsException();
  }

  private Node<T> getNode(int index) {
    Node<T> cursor = head;
    int count = 1;
    while (count <= index) {
      cursor = cursor.next;
      count++;
    }
    return cursor;
  }

  public void add(T data) {
    Node<T> newNode = new Node<>(data);

    if (head == null) head = newNode;
    else {
      Node<T> lastNode = getNode(size() - 1);
      lastNode.next = newNode;
    }
  }

  public T get(int index) {
    checkIndex(index);
    return getNode(index).data;
  }

  public void remove(int index) {
    checkIndex(index);
    if (index == 0) head = head.next;
    else {
      Node<T> prevNode = getNode(index - 1);
      prevNode.next = prevNode.next.next;
    }
  }

  public void insert(int index, T data) {
    checkIndex(index);
    Node<T> newNode = new Node<>(data);
    if (index == 0) {
      newNode.next = head;
      head = newNode;
    } else {
      Node<T> prevNode = getNode(index - 1);
      newNode.next = prevNode.next;
      prevNode.next = newNode;
    }
  }
}

class Node<T> {
  T data;
  Node<T> next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}