[CM202] 04. 연결 리스트 (Linked List)

배열의 문제점

 우리는 앞서 가장 기본적인 데이터 구조인 배열에 대해 살펴 보았습니다. 그리고 배열을 이용해 연산을 하는 과정이 조금 번거로운 것도 알게 되었죠. 배열은 그 크기와 위치가 고정되어 있는 탓에 유연하게 다루기가 어려웠습니다.

 이러한 문제점을 해결하기 위해 새로운 데이터 구조를 고안할 필요가 있습니다. 이번에는 리스트를 구현할 수 있는 또 다른 데이터 구조인 연결 리스트에 대해 살펴봅시다.

연결 리스트 (Linked List)

 연결 리스트 (Linked List)는 값을 저장한 객체들이 다음 값을 가진 객체의 주소를 함께 가리키는 자료구조입니다. 이 객체는 기본적으로 두 가지 값을 가집니다. 우리가 실제로 저장하는 데이터와 객체의 다음 주소값입니다. 단, 리스트의 가장 끝에 해당하는 꼬리(tail)는 다음 주소값 없이 데이터만 가집니다. 이 객체 구조를 노드(node)라고 부릅니다.

// 노드
private static class Node {
  private String element;   // 노드가 저장하는 데이터
  private Node next;        // 다음 노드의 주소값
}

// 연결 리스트
Node third = new Node();      // 꼬리 부분
third.element = "cookie";     // 데이터는 있지만
third.next = null;            // 다음 주소값을 가지지 않음

Node second = new Node();     // 두 번째 노드
second.element = "chocolate";
second.next = third;

Node first = new Node();      // 첫 번째 노드 (머리)
first.element = "macaron";
first.next = second;

 각 노드들이 자기 다음에 올 노드가 무엇인지 알고 있으니, 연결리스트는 굳이 연속적인 공간에 저장될 필요가 없습니다.

 정리하자면, 연결 리스트의 대표적인 특징은 다음과 같습니다.

• 메모리 공간이 불연속적이다.
• 크기가 유동적으로 변한다
• 인덱스를 사용한 접근에 순회가 필요하다.

데이터 구조: SinglyLinkedList

 이제 원리를 알았으니, 클래스를 이용해 구현해볼 차례입니다. 우선 연결리스트는 노드를 최소 단위로 하니까 노드 객체에 대한 클래스를 먼저 정의해야겠죠. 앞서 코드를 통해 소개했지만, 몇 가지 기능을 더 추가하여 정의해보겠습니다.

Node - 멤버

이름	자료형	기능
element	E	값
next	Node<E>	다음 요소

Node - 메소드

이름	매개변수	반환값	기능
getElement()	-	E	값 가져오기
getNext()	-	Node<E>	다음 노드 가져오기
setNext()	Node<E> n	-	다음 노드 설정하기

클래스 이름 다음에 오는 <E>는 제네릭이라고 하는 Java의 문법입니다. 이는 E가 어떤 자료형이라도 된다는 뜻입니다. 예를 들어, <String>으로 사용하면 그 뒤의 E는 모두 String 자료형이 적용됩니다.

 이제 연결 리스트를 구현하기 위해서 어떤 멤버와 메소드가 필요한지 정의합시다.

SinglyLinkedList - 멤버

이름	자료형	기본값	기능
head	Node<E>	-	첫 번째 요소
tail	Node<E>	-	마지막 요소
size	int	0	길이

SinglyLinkedList - 메소드

이름	매개변수	반환값	기능
reverse()	-	-	순서 반전
size()	-	int	길이 반환
isEmpty()	-	boolean	비어 있는지 여부
contain(E e)	e : 요소	boolean	e를 포함하는지 여부
count(E e)	e : 요소	int	e의 개수 반환
getFirst()	-	E	머리(head) 반환
getLast()	-	E	꼬리(tail) 반환
addFirst(E e)	e : 요소	-	맨 앞에 요소 추가
addLast(E e)	e : 요소	-	맨 뒤에 요소 추가
removeFirst()	-	E	맨 앞의 요소 빼서 반환
removeLast()	-	E	맨 뒤의 요소 빼서 반환

메소드 살펴보기

 이 중에서 주의 깊게 보아야 할 함수인 add와 remove 함수들에 대해 좀 더 살펴봅시다.

addFirst( )

public void addFirst(E e) {
  Node<E> newest = new Node<>(e, head); // 값이 e이고 다음 노드가 head
  if (isEmpty()) {  // 만약 비어 있었다면
    tail = newest;  // 새 노드가 head이면서 tail
  } 
  head = newest;  // head를 새 노드로 교체
  size++;  // 크기 한 칸 증가
}

addLast( )

public void addLast(E e) {
  Node<E> newest = new Node<>(e, null); // 값이 e이고 다음 노드가 없음
  if (isEmpty()) {  // 만약 비어 있었다면
    head = newest;  // 새 노드가 head이면서 tail
  }
  else {  // 비어 있지 않다면
    tail.setNext(newest);  // 새 노드는 tail의 다음이 됨
  } 
  tail = newest;  // tail을 새 노드로 교체
  size++;  // 크기 한 칸 증가
}

removeFirst( )

public E removeFirst(E e) {
  if (isEmpty()) {  // 비어 있다면 반환할 노드가 없으므로
    return null;  // null 반환
  }
  E answer = head.getElement();  // 반환할 노드 값

  head = head.getNext();  // 이제 그 다음 노드가 head가 됨
  if (size == 1) {  // 만약 아무것도 남지 않는다면 (길이 1)
    tail = null;  // tail도 없는 노드 처리
  }
  size--;  // 크기 한 칸 감소

  return answer;
}

removeLast( )

public E removeLast(E e) {
  if (isEmpty()) {  // 비어 있다면 반환할 노드가 없으므로
    return null;  // null 반환
  }
  // tail의 이전 값을 알려면 순회를 해야 합니다.
  Node<E> point = head;  // 순회를 위한 추적값
  E answer = tail.getElement();  // 반환할 노드 값

  while (true){
    if (point.getNext() == tail){  // point의 다음이 tail이라면
      tail = point;  // 이제 point가 tail이 됨
      point.setNext(null);  // point 다음은 없는 노드
      break;
    }

    if (size == 1){  // 만약 아무것도 남지 않는다면 (길이 1)
      head = null;  // head는 없는 노드 처리
      tail = null;  // tail도 없는 노드 처리
      break;
    }

    point = point.getNext();  // 순회
  }
  size--;  // 크기 한 칸 감소

  return answer;
}

 연결리스트는 연속된 고정공간이라는 제약을 극복하여 배열의 문제점을 해결할 수 있는 데이터 구조입니다. 무엇보다도 필요에 따라 크기를 바꿀 수 있는 동적 구조라는 점에서 많이 쓰이게 됩니다. 하지만 무작위 접근을 위해서 순회가 필요하다는 단점도 있습니다. 배열의 완벽한 상휘호한은 아니라는 뜻이죠.

	배열	연결 리스트
공간	연속적	불연속적
크기	고정됨	동적
무작위 접근	빠름	느림

전체 코드 보기

public class SinglyLinkedLIst<E> {
  // nested class: Node
  private static class Node<E> {
    // member
    private E element;
    private Node<E> next;

    // constructor
    public Node(E e, Node<E> n) {
      element = e;
      next = n;
    }

    // methods
    public E getElement() { return element }
    public Node<E> getNext() { return next }
    public void setNext(Node<E> n) { next = n; }
  }

  // member
  private Node<E> head;
  private Node<E> tail;
  private int size;

  // constructor
  public SinglyLinkedList() {
    head = null;
    tail = null;
    size = 0;
  }

  // methods
  public int size() { return size }

  public boolean isEmpty() { return size == 0 }

  public E first() {
    if (isEmpty()) { return null }
    return head.getElement();
  }

  public E last() {
    if (isEmpty()) { return null }
    return tail.getElement();
  }

  public void addFirst(E e) {
    Node<E> newest = new Node<>(e, head);
    if (isEmpty()) { tail = newest; } 
    head = newest;
    size++;
  }

  public void addLast(E e) {
    Node<E> newest = new Node<>(e, null);
    if (isEmpty()) { head = newest; }
    else { tail.setNext(newest); } 
    tail = newest;
    size++;
  }

  public E removeFirst(E e) {
    if (isEmpty()) { return null }
    E answer = head.getElement();

    head = head.getNext();
    if (size == 1) { tail = null; }
    size--;

    return answer;
  }
}