[자료 구조] 싱글 링크드 리스트(Singly Linked List)

자바 예제로 설명하는 싱글 링크드 리스트(Singly Linked List)

링크드 리스트(Linked List) 란?

Linked List 는 데이터와 다음 노드를 가리키는 주소를 가진 노드들의 배열로 이루어진 자료구조 이다. 즉 각각의 노드는 다른 노드를 참조하게 되어, 한 노드를 통해 다른 노드에 접근이 가능하다. 이로써 전체적으로 보았을때 각각의 노드는 첫노드와 끝노드를 잇는 체인(chain)을 구성하게 된다.

그렇다면 싱글 링크드 리스트(Singly Linked List)란?

우리는 각각의 노드들이 본인의 다음 노드의 주소만을 가지고 있을 때 그것을 Singly Linked List 라 한다.

싱글 링크드 리스트 예제

위 그림을 보자. 각각의 노드들은 데이터와 다음 노드의 메모리 주소로 이루어져 있다. 그렇게 한 노드를 통해 다음 노드를 참조할 수 있게 되고, 결국에는 추상적인 배열을 이루게 된다. 추상적 배열이라 적은 이유는, 실제로 메모리 내에는 각각의 노드들이 제각각의 위치에 저장되기 때문이다.

링크드 리스트에는 Head와 Tail 이라 불리는 특별한 노드 인스턴스들이 존재하는데 이름에서 알 수 있듯이, Head 는 가장 첫 번째 노드를 가리키고 Tail 은 가장 마지막 노드를 가리킨다.

우리가 노드에 인터져 값을 저장한다 가정할 때, 그 Node 클래스는 아래와 같이 구현될것이다
아래는 Node 클래스의 자바 예제임

public class Node {
 private int data;
 private Node nextNode;
 
 public Node(int data) {
  this.data = data;
 }

 public Node(int data, Node nextNode) {  
  this.data = data;
  this.nextNode = nextNode;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getNextNode() {
  return nextNode;
 }

 public void setNextNode(Node nextNode) {
  this.nextNode = nextNode;
 } 
}

아래는 싱글 링크드 리스트의 메소드들의 Big O 복잡도 이다

Operation 이름	Big O 복잡도
addHead(int t)	O(1)
addTail(int t)	O(1)
search(int t)	O(n)
remove(int t)	O(n)
removeHead()	O(1)
removeTail()	O(n)
clear()	O(1)
isEmpty()	O(1)

시작하기전에 SinglyLinkedList의 컨스트럭터와 인스턴스 변수들을 보고 가자.

public class SinglyLinkedList {
 private Node head, tail;

 public SinglyLinkedList() {
  head = null;
  tail = head;
 }
}

void addHead(int t)

싱글 링크드 리스트 addHead 메소드

이 메소드는 파라미터 값으로 주어진 인터져 t 를 이용해 새로운 노드를 만든 다음 리스트의 가장 첫번째 위치(Head)에 넣는다. Head라는 인스턴스로 가장 첫번째 노드의 레퍼런스를 가지고 있으므로 이 오퍼레이션은 O(1)의 Efficiency 로 실행 가능하다.
아래는 자바 예제이다

public void addHead(int t) {
  Node tmp = new Node(t, head);
  head = tmp;
  if (tail == null) {
   tail = head;
  }
 }

addHead 메소드는 인터져 t 를 파라미터로 받아, 데이터 값으로 t 를 가지고 다음 노드를 가리크는 레퍼런스 값으로 head의 주소를 가지는 새로운 노드 tmp 를 만들게 된다. 그리고 나서 우리는 head 값이 tmp 의 레퍼런스를 가리키게 만들게 된다. 그리고 tail 노드의 값이 만약 null 이라면, 이는 현재 리스트에 있는 노드의 수가 1개 밖에 없다는 것이니, tail 이 head를 가리키게 만든다.

void addTail(int t)

싱글 링크드 리스트 addTail 메소드

이 메소드는 파라미터 값으로 주어진 인터져 t 를 이용해 새로운 노드를 만든 다음 리스트의 가장 마지막 위치(Tail)에 넣는다. Tail라는 인스턴스로 가장 마지막 노드의 레퍼런스를 가지고 있으므로 이 오퍼레이션 또한 O(1)의 Efficiency 로 실행 가능하다.
아래는 자바 예제이다

public void addTail(int t) {
  Node tmp = new Node(t);
  if (isEmpty()) {
   head = tmp;
                        tail = head;
  } else {
   tail.setNextNode(tmp);
   tail = tail.getNextNode();
  }
 }

addHead 메소드와 같이, 우리는 주어진 인터져 t 로 새로운 노드 tmp 를 만들며 시작한다. 그리고 isEmpty 메소드를 이용해 리스트가 지금 empty 상태인지 확인한다. 만약 리스트가 텅 빈상태라면, 그져 새로운 노드를 head 인스턴스에 어싸인하고 tail 인스턴스가 head 인스턴스를 참조하게 만드는것이면 충분하다.
만약 리스트가 empty 상태가 아닐경우에, 우리는 우선 현재 tail 노드(곧 마지막에서 2번째 노드가 될 노드)의 다음노드로 tmp 노드를 참조케 한후, tail 인스턴스가 아까 어싸인한 tmp 노드를 참조하게 한다.

int search(int t)

이 오퍼레이션은 리스트에서 t 값을 가진 노드를 검색하여 그 중 가장 처음에 나오는 노드의 index 를 리턴하는 메소드 이다.

public int search(int t){
  Node pointer = head;
                int indexOfElement = -1;
                int traverseIndex = 0;
  while(pointer!=null)
  {
   if(pointer.getData()==t)
   {
    indexOfElement = traverseIndex;
    break;
   }
   pointer = pointer.getNextNode();
                        traverseIndex++;
  }
  return indexOfElement;
 }

정렬되지 않은 리스트에서 검색 작업은 언제나 모든 노드들을 읽는 작업 이다. 이는 Traverse 라 불리는데 그렇기 때문에, 언제나 O(n)의 efficiency 를 가진다.
우리는 우선 포인터로 쓸 노드를 만듬으로써 이 메소드를 시작해아한다. 만약
'head = head.getNextNode()'
라는 코드로 리스트를 traverse 해버리면 우리는 저 코드가 처음 실행되는 순간, 원래 head 의 위치를 잃어버리게 될것이고 결국 리스트는 엉망이 되어 버릴것이니다. 그렇니 traverse 작업중에 pointer 로 쓸 노드를 만들어 두고 시작하자.
우선 우리의 pointer 노드가 head와 같은 위치를 참조한 상태에서 시작한다. 그리고 looping을 하면서 우리가 원하는 값이 발견될 때까지, 발견되지 않는다면 리스트의 마지막 노드까지 traverse 작업을 하게 된다.

void removeHead()

싱글 링크드 리스트 removeHead 메소드

이 메소드는 head 노드를 제거하고 head 인스턴스가 2번째 노드를 참조하게 만드는 메소드 이다.

public void removeHead() {
  if (head == tail) {
   clear();
  } else {
   head = head.getNextNode();
  }
 }

만약 head == tail 이라는 컨디션이 참이라면, 이는 리스트에 1개의 노드가 있거나 head 와 tail 이 둘다 null 임을 의미하니, 그냥 clear method 를 이용해서 리스트를 empty 상태로 만들어주면 된다.
만약 그렇지 않다면, 그냥 head의 다음 노드의 주소를 가져와, head 가 그 주소를 참조하도록 만들어야한다.

void removeTail()

싱글 링크드 리스트 removeTail 메소드

이 메소드는 tail 인스턴스가 참조하는 가장 마지막 노드를 제거한다.

public void removeTail() {
  if (head == tail) {
   clear();
  } else {
   Node pointer = head;
   while (pointer.getNextNode() != tail) {
    pointer = pointer.getNextNode();
   }
   tail = pointer;
   tail.setNextNode(null);
  }
 }

Singly linked list 에서 전 노드에 엑세스할 방법은 head 에서부터 다시 traverse 하는 방법 뿐이다. removeHead 메소드와는 달리 이 작업을 완료하기 위해서는 tail 노드의 바로 전 노드의 reference 필드를 수정해야한다.
그렇기 때문에, 다시 pointer 노드를 이용해서 tail 노드의 바로 전 노드 까지 이동한다.
그리고 나서, pointer 노드 인스턴스가 참조하는 마지막에서 2번째 노드를 tail 인스턴스에 어싸인해준다. 그후에 tail.setNextNode(null) 메소드를 이용해서 원래 2번째 마지막 노드가 가지고 있는 마지막 노드의 주소 필드를 null 로 바꿔주면 끝~

void remove(int t)

싱글 링크드 리스트 remove 메소드

이 메소드는 int t 값을 가진 노드 중 가장 앞에 존재하는 노드를 제거한다.

public void remove(int t) {
  if (!isEmpty()) {
   if (head == tail&&head.getData()==t) {
    clear();
   } else {
    Node pointer = head;
    while (pointer != null) {
     if (pointer.getNextNode().getData() == t) {
      pointer.setNextNode(pointer.getNextNode().getNextNode());
      break;
     }
     pointer = pointer.getNextNode();
    }
   }
  }
 }

첫번째로, 리스트가 Empty 상태인지 확인해야한다, 위 코드에는 나와있지 않지만 만약 Empty 상태이면 nullpointerexception 이나 다른 exception 을 던져야한다. 그리고 만약 empty 상태가 아니라면, 다음으로 head 와 tail 인스턴스가 같은 노드를 참조하고 있는지, 그리고 참조하는 노드의 데이터가 t 와 일치하는지를 비교한후, 일치한다면, 이는 리스트에 노드가 1개밖에 없다는 것이므로 clear 메소드를 이용해서 리스트를 empty 시킨다.
만약 그렇지 않다면 t 값을 가진 노드를 찾아서 리스트의 끝으로 traverse 하고, 노드를 찾았을 때 "pointer.setNextNode(pointer.getNextNode().getNextNode())".를 이용해서 노드가 참조하는 참조값을 수정하여 리스트에서 제거한다.

아래는 clear 메소드와 isEmpty 메소드를 자바로 구현한것이다.

private void clear() {
  head = tail = null;

 }

 private boolean isEmpty() {
  if (head == null) {
   return true;
  } else {
   return false;
  }
 }