[자료구조][Java] 연결리스트/링크드 리스트(Linked List)

1. 링크드 리스트 (Linked List) 구조

• 연결 리스트라고도 함
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조
• 링크드 리스트 기본 구조와 용어
  • 노드(Node) : 데이터 저장 단위 ( 데이터 값 + 포인터 ) 로 구성
  • 포인터(Pointer) : 각노드 안에서, 다음이나 이전의 노드와의 연결 정보(주소 값)를 가지고 있는 공간
• 링크드 리스트의 장단점
  • 장점 
    • 미리 데이터 공간을 할당하지 않아도 됨
  • 단점
    • 연결을 위한 별도 데이터 공간도 결국엔 필요하므로, 저장 효율이 높다고는 할 수 없음
    • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
    • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
• 일반적인 링크드 리스트 형태

 

2. Java로 링크드 리스트 구현하기

• Node 클래스 구현하기

public class Node<T> {
    T data;
    Node<T> next = null;
    
    public Node(T data) {
    	this.data = data;
    }
}

 

• Node인스턴스 찍어내기

Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node2 = new Node<Integer>(2);

 

• Node와 Node 연결하기 : Node 인스턴스 간 연결 및 가장 첫부분인 head에 node1 대입

node1.next = node2;
Node<Integer> head = node1;

 

• 링크드 리스트에 데이터 추가하기

public void addNode( T data ) {
    if (head == null){
    	head = new Node<T>(data);
    } else {
    	Node<T> node = this.head;
    	while( node.next != null ) {
        	node = node.next;
        } 
        node.next = new Node<T>(data); 
    }
}

 

• 링크드 리스트에서 특정 데이터를 검색하기

public Node<T> search(T data) {
    if (this.head == null ) {
    	return null;
    } else {
    	Node<T> node = this.head;
        while(node != null) {
        	if (node.data == data) {
            	return node;
            } else {
            	node = node.next;
            }
        }
        return null;
    }
}

 

• 링크드 리스트에서 특정 노드 뒤에 값 추가 하기

public void addNodeInside(T data, T isData) {
    Node<T> searchedNode = this.search(isData);
    
    if ( searchedNode == null ) {
    	this.addNode(isData)
    } else {
    	Node<T> nextNode = searchedNode.next;
        searchedNode.next = new Node<T>(data);
        searchedNode.next.next = nextNode;
    }
}

 

• 링크드 리스트에서 특정 노드 삭제하기

public boolean delNode(T isData) {
    if (this.head == null ) {
    	return false;
    } else {
    	Node<T> node = this.head;
        if (node.data == isData) {
            this.head = this.head.next;
            return true;
        } else {
        	while (node.next != null) {
                    if (node.next.data == isData){
                	node.next = node.next.next;
                	return true;
                }
                node = node.next;
            }
            return false;
        }
    }
}

 

• 링크드 리스트 전체 출력하기

public void printAll() {
    if ( head != null ) {
    	Node<T> node = this.head;
        System.out.println(node.data);
        while (node.next != null) {
        	node = node.next;
            System.out.println(node.data);
        }
    }
}

 

• 전체 코드

public class SingleLinkedList<T> {

	public Node<T> head = null;

	public class Node<T>{
		T data;
		Node<T> next;
		
		public Node(T data) {
			this.data = data;
		}
	
	}
	
	public void addNode(T data) {
		if ( head == null) {
			head = new Node<T>(data);
		} else {
			Node<T> node = this.head;
			while (node.next != null) {
				node = node.next;
			} 
			node.next = new Node<T>(data);
		}
	}
	
	public void printAll() {
		if ( head != null) {
			Node<T> node = this.head;
			System.out.println(node.data);
			while ( node.next != null) {
				node = node.next;
				System.out.println(node.data);
			}
		}
	}
	
	public Node<T> search(T data) {
		// head null 체크 -> null 이라면 아무것도 없는 LingkedList이니 null을 리턴한다.
		if (this.head == null) {
			return null;
			
		} else { // head가 null이 아니다 -> 적어도 하나 이상의 노드가 있다.
			
			Node<T> node = this.head; // node에 head 대입
			
			while (node != null) { // 노드가 있으면 계속 반복
				if (node.data == data) { // 노드 안 데이터를 내가 찾고자 하는 데이터와 비교
					return node; // 맞다면 리턴
				} else { 
					node = node.next; // 아니라면 다음 노드로 넘어감
				}
			}
			return null;
		}
	}
	
	public void addNodeInside (T data, T isData) { 
		Node<T> searchedNode = this.search(isData); // isData가 있는지 search메소드를 사용해 찾고, 있다면 해당 노드를 대입
		
		if (searchedNode == null) { // 찾는 노드가 없을 때 
			this.addNode(data); // addNode 메소드로 추가하기 -> 가장 뒤에 추가된다
		} else {
			Node<T> nextNode = searchedNode.next; // 찾은 노드의 다음노드에 새 노드를 추가할거기 때문에 미리 nextNode에 옮겨 둠.
			searchedNode.next = new Node<T>(data); // 찾은 노드의 다음 노드에 새노드 추가.
			searchedNode.next.next = nextNode; // 찾은 노드의 다음다음 노드에 원래 있던 다음 노드 추가.
		}
	}
	
	public boolean delNode(T isData) {
		if (this.head == null) { // head가 null이면 하나의 노드도 있지 않은 것이므로 false 리턴
			return false;
		} else {
			Node<T> node = this.head; // 노드가 하나라도 있다면 헤드 노드 대입
			if (node.data == isData) {  // 노드의 데이터가 지우려는 데이터와 같다면
				this.head = this.head.next; // 헤드의 다음 노드를  헤드로 지정.
				return true;
			} else {
				while (node.next != null) { // 노드의 다음 노드가 있을때 까지 반복
					if (node.next.data == isData) { // 다음 노드의 데이터가 지우려는 데이터와 같다면
						node.next = node.next.next; // 다음 노드의 다음노드는 다음다음 노드로 지정하여 다음노드를 없앤다.
						return true;
					}
					node = node.next; // 다음 노드 설정.
				}
				return false; // 위의 while문을 돌고도 리턴이 안된거면 해당 데이터가 없으므로 false 반환.
			}
		}
	}
	
	public static void main(String[] args) {
		// 테스트 코드
		SingleLinkedList<Integer> MySingleLinkedList = new SingleLinkedList<Integer>();
		
		MySingleLinkedList.addNode(1);
		MySingleLinkedList.addNode(2);
		MySingleLinkedList.addNode(3);
		MySingleLinkedList.addNode(4);
		MySingleLinkedList.addNode(5);
		MySingleLinkedList.printAll();

		MySingleLinkedList.addNodeInside(6, 3);
		MySingleLinkedList.printAll();
		
		MySingleLinkedList.delNode(5);
		MySingleLinkedList.printAll();
	}

}