[Java] 링크드 리스트 (Linked List)

링크드 리스트

링크드 리스트는 각 노드가 데이터와 포인트를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.

데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다.

배열에 비해서 데이터의 추가, 삭제가 용이하지만

인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어진다.

(탐색 또는 정렬을 자주하는 경우엔 배열을 사용 / 데이터의 추가, 삭제가 많은 경우 링크드 리스트를 사용하는것이 좋다.)

링크드 리스트의 경우 인덱스를 사용하여 연산을 수행할 수 있도록 get()형태의 메서드를 제공하지만, 메서드 내부의 동작은 순차 탐색으로 이루어져 있다.

링크드 리스트 구조와 용어

• 노드 (Node) : 데이터 저장 단위(데이터 값, 포인터)로 구성
• 포인터 (pointer) : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

링크드 리스트 형태

장점

데이터 공간을 미리 할당하지 않아도 된다. (배열은 데이터 공간을 할당 해야한다.)

단점

연결을 위한 별도 공간이 필요하다. (저장 공간 효율이 높지 않음)

연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림

중간 데이터 삭제시 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

Node Class 구성하기

위의 그림을 생각하며 코드를 구성하면 접근이 쉽다.

class Node<T> {
  	T data;
  	Node<T> next;  // 레퍼런스 변수
  	
  	public Node(T data) {
      	this.data = data;
      	this.next = null;
    }
  
  	public T getData() {  // Node의 data값을 출력하기 위한 메서드
      	return this.data;
    }
}

개인적으로 공부한 점을 정리하자면

처음에 Node 클래스 안에서 전역변수로 Node next를 선언한 코드를 봤을때 왜 Node안에 Node를 또 선언했을까? 라고 의구심이 들었다.

새로운 노드를 생성하고 다음 노드를 또 새로 생성하게되면 링크드 리스트의 구조상 현재 있는 노드의 next 변수에 새로 생성할 노드의 주소값을

담아줘야 하기때문에 주소값의 type값과 같게 선언해야해서 Node type으로 선언할 수 밖에 없는 사실을 알았다.

LinkedList Class 구성하기

public class LinkedList<T> {
  	private Node<T> head;
  
  	public LinkedList() {
	    head = null;
	}
  
  	// 링크드 리스트 맨뒤에 삽입
  	public void insertNode(T data) {
	    Node<T> newNode = new Node<>(data);
      
	    if (head == null) {
	        this.head = newNode;
	    } else {
	        Node<T> tempNode = head;
          	
	        while (tempNode.next != null) {
	            tempNode = tempNode.next;
  	        }
          
	        tempNode.next = newNode;
	    }
	}
  
  	// 노드 중간에 삽입
  	public void insertNode(T data, T isData) {  // data : 새로 넣은 데이터, isData : 이전 노드 데이터
	    Node<T> search = this.searchNode(isData);
      
	    if (search == null) {  // 찾는 데이터가 없을때
	        this.insertNode(data);  // 마지막 노드로 넣어준다.
	    } else {
          	Node<T> newNode = new Node<>(data);
          	newNode.next = search.next;
          	search.next = newNode;
	    }
	}
  
  	// 노드 찾기
  	public Node<T> searchNode(T data) {
	    if (head == null) {
	        return null;
  	    } else {
  	        Node<T> node = head;
  	        while (node.next != null) {
  	        if (node.data == data) return node;  // 현재 노드와 parameter로 받은 data의 값이 일치한지 체크
  	        else node = node.next;
  	        } 
  	    return null;
  	    }
	}
  	
  	// 링크드 리스트 맨뒤의 노드 삭제
  	public void deleteNode() {
	    Node<T> preNode;
	    Node<T> tempNode;
      
	    if (head == null) {
	        return;
	    }
      
	    if (head.next == null) {
	        head = null;
	    } else {
	        preNode = head;
          	tempNode = preNode.next;
          
          	while (tempNode.next != null) {
              	preNode = tempNode;
              	tempNode = tempNode.next;
	        }
          
          	preNode.next = null;
	    }
	}
  
  	// 중간 노드 삭제
  	public void deleteNode(T data) {
	    Node<T> preNode = head;
	    Node<T> tempNode = preNode.next;
      
	    if (data.equals(preNode.getData())) {  // head의 data와 삭제할 data가 일치할때
          	head = preNode.next;
          	preNode.next = null;
	    } else {
          	while (tempNode != null) {
	            if (data.equals(tempNode.getData())) {
	                if (tempNode.next == null) {  // 마지막 노드인 경우
	                    preNode.next = null;
	                } else {  // 마지막 노드가 아닌 경우
	                    preNode.next = tempNode.next;
	                    tempNode.next = null;
	                }
	                break;
	            } else {
	                preNode = tempNode;
                  	tempNode = tempNode.next;
	            }
	        }
	    }
	}
  
  	// 링크드 리스트 요소 출력
  	public void printAll() {
	    if (head != null) {
	        Node<T> node = this.head;
	        System.out.println(node.getData());
          	
	        while (node.next != null) {
	            node = node.next;
	            System.out.println(node.getData());
	        }
	    }
	}
  
  	public static void main(String[] args) {
	    LinkedList<Integer> l = new LinkedList<>();
	    // 노드 마지막에 추가 해보기
	    l.insertNode(1);
	    l.insertNode(3);
	    l.insertNode(5);
	    l.printAll();
	    System.out.println("==========");
	    System.out.println("중간 노드 삽입");
	    l.insertNode(2, 1);
	    l.insertNode(4, 3);
	    l.printAll();
	    System.out.println("==========");
	    // 노드 마지막꺼 삭제 해보기
	    l.deleteNode();
	    l.deleteNode();
	    l.deleteNode();
	    l.printAll();
	    System.out.println("==========");
	    System.out.println("중간 노드 삭제");
	    l.deleteNode(3);
	    l.printAll();
	}
  }