본문 바로가기

프로그래밍/자료구조/알고리즘

자바로 구현하는 링크드 리스트 (Singley LinkedList)



안녕하세요?

이번 강좌에서는 자바로 제네릭을 통한 단일 연결리스트 (SingleyLinkedList) 를 구현하도록 하겠습니다.

(자바에 대한 기초 사전 지식이 필요합니다. 자료구조는 반드시 기초를 먼저 공부후에 공부하세요!)


우선 자바에서는 java.uitl 패키지안에 다양한 자료구조를 제공하고 있습니다.


그중에서도 LinkedList 클래스 (이중연결리스트) 를 사용하면 아주 편리한 자료구조를 사용 할 수 있습니다.


이렇게 편리하게 이미 링크드리스트를 제공해주지만, 


링크드리스트 자료구조가 내부적으로 어떻게 구현되어있고 어떤식으로 작동하는지 살펴보겠습니다.


우선, 제가 제작한 소스코드는 


 



C로 배우는 쉬운 자료구조 (한빛미디어) 서적의 수도코드 (pseudo code) 를 참고 하였으며,

java.uitl.LinkedList 를 참고하였음을 알려드립니다.



1. 단일연결리스트 란?

 - 리스트를 구현한 데이터 구조의 한 형태. 리스트의 각 노드에 다른 노드를 가리키는 포인터가 하나씩만 있는 것으로, 연결 리스트의 하나이다.

[네이버 지식백과] 단일 연결 리스트 [singly linked list] (컴퓨터인터넷IT용어대사전, 2011.1.20, 일진사)





위와 같이 기차형태로, 꼬리에 꼬리를 무는 형태의 순차 자료구조 입니다.



데이터 필드와 링크필드로 구성된 노드는 순차적으로 다음 노드를 가르키게 됩니다.

가장 앞에 있는 노드를 head 라고 부르며, 가장 마지막에 있는 노드를 tail 이라 부릅니다.

그리고 tail 은 마지막 이므로 링크필드가 null 로 구성되어 있습니다.


우선 코드를 통해 노드를 구성해 보겠습니다.


  1. public class SingleyLinkedList<T> {
  2.  
  3.    
  4.     private Node head; //head Node
  5.     private Node tail; //tail Node
  6.     private int size = 0;
  7.    
  8.    
  9.     class Node {
  10.         private T data; //data field
  11.         private Node link; //link field
  12.        
  13.         private Node(T data, Node link) {
  14.             this.data = data;
  15.             this.link = link;
  16.         }
  17.     }
  18. }


제네릭을 사용하기 위해 어떠한 데이터가 올지 모르니 T를 사용하겠습니다.

단일 연결리스트의 노드로 사용할 노드 이너클래스 하나를 선언하겠습니다.

SingleyLinkedList 클래스의 인스턴스 객체로 head (첫노드), tail (마지막 노드), size (크기) 변수 하나를 선언하겠습니다.

Node 이너클래스의 생성자는 객채생성시 데이터와 다음노드의 주소를 미리 지정 받을 수 있습니다.



1. 첫번째 노드 삽입 연산






첫번째 노드 삽입연산 알고리즘

(1) 새로운 노드를 할당하여, 데이터를 삽입한다.

(2) 새로운 노드의 link 를 현재의 head 노드 로 지정한다.

(3) head 노드를 새로운 노드로 지정한다.


  1.     private void linkFirst(T data) {
  2.        
  3.         //새로운 Node 구성
  4.         final Node newNode = new Node(data, null);     
  5.         newNode.data = data;
  6.        
  7.         //새로운 노드의 link 는 기존의 head 노드
  8.         newNode.link = head;
  9.        
  10.         //기존의 head 를 newNode 로 지정.
  11.         head = newNode;
  12.        
  13.         if (tail == null) { //tail이 null 인경우 데이터가 한번도 삽입되지 않음.
  14.             tail = head;
  15.         }
  16.        
  17.         size++;
  18.     }



tail 이 null 인경우 아직 데이터가 삽입되지 않았으므로, 

처음 데이터 삽입시 tail 은 head 가 됩니다.

그리고 size 를 하나 증가시켜 링크드리스트에 데이터는 1개가 존재함을 저장합니다.



2. 중간 노드 삽입 연산




중간 노드 삽입연산 알고리즘

(1) 새로운 노드를 할당하여, 데이터를 삽입한다.

(2) 새로운 노드의 link 는 position 에 위치한 노드의 이전노드(prev)의 링크로 지정한다.

(3) position 에 위치한 노드의 이전노드의 link 를 새로운 노드로 지정한다.



	private void linkBefore(T data, int index) {

		final Node newNode = new Node(data, null);
		newNode.data = data;

		Node prev = node(index-1);
		newNode.link = prev.link;
		prev.link = newNode;
		
		size++;
	}

중간노드에 삽입이 성공하였으므로 size 를 증가 시킨다.


3. 마지막 노드 삽입 연산



마지막 노드 삽입연산 알고리즘

(1) 새로운노드를 할당하여, 데이터를 삽입한다. (이때 새로운 노드의 link 는 NULL)

(2) tail(마지막 노드)를 찾아 마지막 노드의 link 를 새로운 노드로 지정한다. 


  1.     private void linkLast(T data) {
  2.        
  3.         final Node newNode = new Node(data, null);
  4.         newNode.data = data;
  5.        
  6.         if (head == null) {        
  7.             head = newNode;
  8.             tail = newNode;        
  9.         } else {
  10.             tail.link = newNode;
  11.             tail = newNode;
  12.         }
  13.        
  14.         size++;
  15.     }


소스코드에서 마지막 tail 인스턴스 객체에 newNode 지정한 이유는 새로운노드가 마지막 노드에 삽입

되기 때문에 tail 인스턴스를 newNode 로 지정한것이며,

마지막에 삽입이 정상적으로 이루어졌기 때문에 size 를 증가시킨다.


4. 첫번째 노드 삭제 연산



첫번째 노드 삭제연산 알고리즘

(1) head 첫 노드를 temp 로 임시 저장한다.

(2) head 를 temp의 link 로 지정한다. (2번째 노드가 head 가 되기 위함)

(3) temp 를 메모리에서 해제 한다.


  1.     private T unlinkFirst(Node f) {
  2.        
  3.         //f 는 head 첫번째 노드
  4.         T tempData = f.data//삭제될 데이터를 리턴할 임시 객체
  5.        
  6.         Node tempNode = f; //head의 첫노드를 임시로 저장
  7.         head = tempNode.link//head는 임시저장된 head의 다음 노드로 지정
  8.    
  9.         //help gc
  10.         f = null;
  11.         tempNode = null;
  12.  
  13.         size--;
  14.        
  15.         return tempData;
  16.     }



5. 중간 노드 삭제 연산



중간 노드 삭제연산 알고리즘

(1) 특정 포지션 노드의 이전노드(prev)를 구해온다.

(2) 이전노드의 link 를 특정 포지션 노드의 link 로 지정한다.

(3) 현재 노드는 메모리에서 해제한다. 


  1.     private Node node(int index) {
  2.         Node temp = head; //head 노드를 임시로 저장
  3.        
  4.         //index 만큼 돌면서 포지션의 Node에 접근하여 해당 노드 리턴
  5.         for (int i=0;i<index;i++) {
  6.             temp = temp.link;
  7.         }      
  8.         return temp;       
  9.     }
  10.    
  11.     private T unlink(int index) {
  12.         Node old = node(index-1)//포지션의 이전 노드를 구해옴.
  13.         Node current = old.link//이전노드의 link는 현재 포지션의 노드이므로, 임시 저장한다.
  14.         T temp = current.data//삭제하면서 반환될 임시 데이터
  15.         old.link = current.link//이전노드의 link는 현재노드의 link로 지정한다.   
  16.        
  17.         current = null//help gc
  18.        
  19.         size--;
  20.        
  21.         return temp;
  22.     }


6. 노드 검색 연산



노드 검색 알고리즘

(1) 처음 노드부터 특정 포지션만큼 반복하여 노드를 찾는다.

(특정 노드를 탐색하려면 리스트의 노드를 처음부터 하나씩 순회하면서 노드를 찾아야 합니다.)


  1.     private Node node(int index) {
  2.         Node temp = head; //head 노드를 임시로 저장
  3.        
  4.         //index 만큼 돌면서 포지션의 Node에 접근하여 해당 노드 리턴
  5.         for (int i=0;i<index;i++) {
  6.             temp = temp.link;
  7.         }      
  8.         return temp;       
  9.     }


java.util.LinkedList 에서도 get 이라는 메서드로 포지션에 해당하는 노드를 찾습니다.

포지션으로 찾는 이유는 내가 찾고자 하는 데이터필드가 다른 노드와 중복될수 있기 때문입니다.

따라서, 데이터를 찾는 검색 메소드는 제공하지 않습니다.

(필요하면 직접 구현해서 사용하시면 됩니다.)



<실행결과>

  1.     public static void main(String[] args) {
  2.        
  3.         SingleyLinkedList<Integer> linkedList = new SingleyLinkedList<Integer>();
  4.         linkedList.add(02);  
  5.         linkedList.add(14);
  6.         linkedList.add(25);
  7.         linkedList.remove(2);  
  8.         linkedList.display();  
  9.  
  10.         System.out.println("\nFirst : " + linkedList.getFirst().toString());
  11.         System.out.println("Last : " + linkedList.getLast().toString());
  12.        
  13.     }




SingleyLinkedList.java



PS. 강좌 목적으로 제작한 소스코드이기 때문에 실제 사용시 문제가 될 수 있음을 알려드립니다.

소스코드의 수정과 배포는 자유롭게 하시면 됩니다.

단, 맨위에 있는 주석은 지우지마세요!

(추후 버그나 이슈에 대한건 피드백 주시면 수정해드리겠습니다.)