단일 연결 리스트(Singly Linked List) 특징, 장단점, 생성, 탐색

단일 연결 리스트는 각 노드가 연결 리스트의 다음 노드를 가리키는 링크가 하나만 있는 연결 리스트입니다.

 

단일 연결 리스트의 특징

• 데이터와 다음 노드의 대한 참조가 들어있습니다.
• 첫 번째 노드에 해당하는 헤드와 마지막 노드에 해당하는 꼬리 포인터에는 null이 있습니다.
• 인접한 메모리 블록에 저장되지 않지만 각 노드에는 다음 노드의 주소가 있습니다.
• 원하는 노드에 접근하기 위해서는 리스트를 헤드부터 순회해야합니다.

단일 연결 리스트의 장점

• 동적 메모리 할당을 허용합니다. 노드가 추가되거나 삭제됨에 따라 런타임에서 리스트의 크기가 변경될 수 있습니다.
• 노드가 별도의 캐시 라인에 저장되어 캐시 누락을 줄이고 캐시 성능을 향상시킬 수 있습니다.
• 연속 메모리 블록이 아닌 노드에 대한 참조만 저장하면 되므로 공간 효율적입니다.

단일 연결 리스트의 단점

• 노드에 접근하기 위해서는 헤드부터 원하는 노드까지 탐색해야 됩니다.
• 다음 노드를 저장하기 위한 메모리가 필요합니다.
• 다음 노드 포인터가 손실되면 데이터 손실됩니다.
• 병렬 처리에 적합하지 않습니다.
• 역방향 탐색이 불가능합니다.

단일 연결 리스트 생성

static class Node {
    int data;
    Node next;	
}

단일 연결 리스트 탐색

public class SinglyLinkedList {
	public static void main(String[] args) {
		Node head = new Node(1);
		Node two = new Node(2);
		head.next = two;
		Node three = new Node(3);
		two.next = three;
		printList(head);
	}
	static class Node {
		int data;
		Node next;
		
		Node(int d) {
			this.data = d;
			this.next = null;
		}		
	}
	static void printList(Node n) {
		while(n != null) {
			System.out.println(n.data);
			n = n.next;
		}
	}
}