[자료구조] 자바 java.util.LinkedList의 주요 메소드 정리

 

이 글은 java.util. LinkedList 를 공부하면서 중요하다고 생각되는 메소드를 정리하였다.

 

 

 

1. Constructor 

public class LinkedList{
    private Node head; //첫번째 노드
    private Node tail; //마지막 노드
    private int length; //노드의 수
    
    class Node{ // Linked List 내부에 Node가 nested 클래스로 들어있음 
    	int value; // 데이터
        Node next;// 포인터 
        
        Node(int value){ // Node생성자 , 데이터를 파라메터로 받음 
        	this.value = value;  
        }
    }
    
    public LinkedList(int value){ // LinkedList의 생성자 
    	Node newNode = new Node(value); //노드에 전달
        head = newNode;
        tail = newNode;
        length = 1; 
    
    }
	

}

• LinkedList의 생성자
  - value를 파라메터로 전달받는다.
  - Node 인스턴스에 value값을 전달하여 newNode 인스턴스를 생성한다. 
  - head와 tail을 newNode로 설정한다.
  - 처음 생성시 노드는 한개이기 때문에 length는 1이다.
• nested class로 되있는 Node 클래스 
  - LinkedList 내부에 nested class로 들어있다.
  - value 속성은 노드의 데이터를 저장한다 ( 여기서는 integer를 지정하였지만 String,float 등등 링크드리스트 인스턴스를 만들 떄 인자값의 데이터 타입에 따라 바뀔 수 있음) 
  - Node객체의 next 필드값은 링크드리스트의 다음 노드를 가리킨다 (처음 생성시 적용되는거라서 포인터는 값이 설정되지 않았음) 
  - 생성자는 value를 전달받고 Node를 생성한다.

 

2. Append 

public void append(int value){  

   Node newNode = new Node(value);

   if(length == 0){ //리스트가 비어있을 때(처음 생성시)
    	head = newNode; 
        tail = newNode;
    }else if(length > 0){ //리스트에 이미 노드가 있을 때
    	tail.next = newNode;  //새로운 노드를 tail노드의 포인터로 추가함 
        tail = newNode; //새로운 노드를 tail로 설정 
    }
    
    length++; //노드추가가 되니 길이가 +1이 된다.

}

LinkedList 끝에 노드를 추가하는 메소드이다. 끝에 새로운 노드가 추가되는 것이니 tail은 newNode가 되고, 기존의 tail의 포인터는 newNode를 가리키도록 업데이트한다. 

 

 

3.Remove Last

public Node removeLast(){
   if(length == 0) return null;
    
    Node temp = head; 
    Node pre = head; 
    
    //마지막 노드까지 반복
    while(temp.next != null){ 
    	pre = temp; // 현재노드
        temp = temp.next; // 현재 노드의 다음 노드 
    }
    
    tail = pre; // tail을 마지막의 이전 노드로 설정 
    tail.next = null; // 마지막 노드를 삭제 
    length--; //노드가 삭제되니 길이 -1이 된다 
    
    if(length == 0){ //모두 삭제된 경우 
    	head = null;
        tail = null;
    }
    
    return temp; //제거된 마지막 노드 반환 


}

pre는 현재 노드를 가리키고 temp는 현재노드의 다음 노드를 가리킨다. 마지막 노드를 삭제하는 메소드니까 pre를 tail값에 주고 tail.next = null 처리를 하여 마지막 노드를 삭제한다.

 

4.Prepend 

public void prepend(int value){
   Node newNode = new Node(value);
    
    if(length == 0){ 
    	head = newNode;
        tail = newNode;
    }else{ //노드가 이미 있을 때
    	newNode.next = head; // 새로운 노드의 포인터는 기존의 head를 가리킴
        head = newNode; //head는 새로운노드가 된다
    }
    
    length++;
}

LinkedList의 맨앞에 노드를 추가하는 메소드이다.  newNode의 포인터는 기존의 head노드를 가리키도록 변경하고 head노드는 newNode가 되도록 설정한다. 

 

5. Remove First 

public void removeFirst(){
	
    if(length == 0) return null;
    
    Node temp = head;
    head = head.next; // 현재 head의 다음노드를 head로 설정 
    temp.next = null; // 이전 head의 포인터를 null로 설정 
    length--;
    if(length==0) tail = null;
    
    return temp;

}

LinkedList의 첫번쨰 노드를 삭제하는 메소드이다. 현재의 head를 head.next로 설정하여 다음 노드를 현재 head로 업데이트 시키고 , temp.next = null을 이용하여 업데이트 전의 노드의  포인터를 null로 설정하여 연결을 끊는다. 

 

6.Get

public Node get(int index){
	if(index < 0 || index >= length){ //인덱스가 유효범위를 초과
    	return null;
    }
    
    Node temp = head; // head 노드부터 시작 
    
    for(int i=0; i<index; i++){
    	temp = temp.next;
    }
    
	return temp;

}

내부적으로 인덱스 0부터 시작하기 때문에 index와 linkedList 길이가 일치한다면 out of boundry처리가 된다.

get()메소드는 인덱스를 이용해서 해당위치의 노드를 찾아서 반환해주지만 실제로는 LinkedList 에서 인덱스를 직접적으로 지원하고 있지는 않다. array와는 다르게 모든 노드를 탐색하기 때문에 O(n)의 시간이 소요된다.

 

7.Set

public boolean set(int index,int value){
	Node node = get(index);
    if(node != null){
    	node.value = value;
        return true;
    }else{
    	return false;
    }

}

특정 인덱스의 노드의 value를 업데이트 시켜주는 메소드이다. get() 메소드를 이용하여 노드를 가져오고 value를 업데이트한다.

 

8.Insert

public boolean insert(int index,int value){
	if(index < 0 || index > length ){ //인덱스 범위를 벗어남
    	return false;
    }else if(index == 0){ // LinkedList의 가장 첫번쨰 노드 
    	prepend(value);
        return true;
    }else if(index == length){ //LinkedList의 가장 마지막 노드 
    	append(value);
        return true;
    }
    
    //인덱스의 첫번째 / 마지막이 아닌 임의의 인덱스에 추가하는 경우 
    Node newNode = new Node(value);
    Node temp = get(index-1); // 추가하려는 인덱스의 이전 노드 
    newNode.next = temp.next; // 새로운 노드의 포인터를 이전 노드의 포인터로 업데이트 
    temp.next = newNode; // 이전노드의 포인터는 새로운 노드가 됨
    length++;
    return true;
}

임의의 인덱스에 노드를 추가하는 메소드이다. get(index-1)을 이용하여 추가하려는 인덱스의 이전 노드를 가져오고 , 새로운 노드의 포인터를 이전노드가 가지고 있던 포인터로 변경한다. 그리고 이전 노드는 새로운 노드를 가리키도록 설정한다. 

 

9.Remove 

public Node remove(int index){
   if(index < 0 || length <= index ){
      return null;
    }else if(index == 0){ //첫번쨰 노드 삭제시 
    	return removeFirst;
    }else if(index == (length-1)){ //마지막 노드 삭제시 
    	return removeLast();
    }
    
    Node preNdoe = get(index-1); // 삭제할 노드의 이전 노드를 가져옴
    Node temp = preNode.next; // 삭제할 노드
    
    preNode.next = temp.next; // 삭제할 노드의 포인터를 이전 노드의 포인터로 업데이트 
    temp.next = null;
    length--;
    return temp;
}

특정 인덱스의 노드를 삭제하는 메소드이다. temp를 삭제할 노드로 설정해주고 temp.next= null을 이용하여 연결을 끊어준다. 

 

10.Reverse

public void reverse(){
	//head와 tail 변경 
    Node temp = head;
    head = tail;
    tail = temp;
    
    Node after = temp.next; //다음노드 
    Node before = null; //이전 노드 

   for(int i=0;i<length;i++){ //포인터 방향변경 ,  노드 수만큼 반복 
    	after = temp.next; 
        temp.next = before;
        before = temp;
        temp = after;
    }

}

LinkedList의 노드 순서를 뒤바꾸는 메소드이다.

1. LinkedList의 head와 tail을 변경한다.
     temp 변수를 활용하여 변경한다. a) Node temp = head으로  temp에 head를 저장하고 b) head = tail로   head는 tail로 업데이트해주고 마지막으로 c) tail = temp를 이용하여 tail이 temp(head)로 업데이트 된다.   
2. head와 tail을 제외한 각각의 노드의 포인터 방향을 반대로 변경한다.
   before는 이전노드 나타내고 , 처음에는 null로 셋팅한다. temp는 현재 노드를 나타내고 after는 다음노드를 나타낸다. for문을 이용하여 포인터의 방향을 변경한다. a) after = temp.next로 after는 현재 노드의 다음을 가리킨다. b) 현재노드의 다음 포인터는 before를 가리킨다. (여기서 포인터의 방향이 반대로 변경되었다) c) before = temp는 이전노드가 현재 노드가 된다. d) temp= after 현재노드는 다음 노드를 가리킨다. 
   이런식으로 노드의 수만큼 반복되면 포인터의 방향이 반대로 변경된다. 
    

 

 

그림으로 표현하면 이런식으로 포인터의 방향이 변경된다.