연결 리스트는 차례로 연결된 노드를 표현해주는 자료구조이다.
연결 리스트는 단방향과 쌍뱡향이 있고 연결리스트 탐색 시간은 k개의 노드가 존재한다고 할때 O(K)만큼 발생한다.

표1 배열, 연결리스트 장점 및 단점

연결리스트의 종류

단일 연결 리스트(Singly Linked List)

각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트입니다.
일반적으로 큐를 구현할 때 사용됩니다.
Head 노드를 잃어버려 참조하지 못하는 경우 데이터 전체를 사용 못하게 되는 단점이 있습니다.
FAT 파일 시스템이 단일 연결 리스트로 파일 청크(동적 메모리로 할당되는 영역)를 연결합니다.

이중 연결 리스트(Doubly Linked List)

각 노드가 이전 노드, 다음 노드에 대해서 참조하는 형태의 연결 리스트입니다.
삭제가 간편하며 단일 연결 리스트에 비해 데이터 손상에 강하지만, 관리할 참조가 2개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많아집니다.

원형 연결 리스트(Circular Linked List)

연결 리스트에서 마지막 요소가 첫번째 요소를 참조합니다.
스트림 버퍼의 구현에 많이 사용됩니다.

연결 리스트 만들기

자바는 C와 달리 링크드리스트를 라이브러리로 import해올수 있다.
링크드리스트를 사용하지 않고 단방향 연결 리스트를 구현하였다.

class Node{
	Node next=null;
	int data;
	public Node(int d) {
		data=d;
	}
	
	void appendToTail(int d) {
		Node end = new Node(d);
		Node n = this;
		while(n.next != null) {
			n=n.next;
		}
		n.next=end;
	}
}

Node deleteNode(Node head, int d) {
	Node n=head;
	if(n.data==d) {
		return head.next;
	}
	while (n.next!=null) {
		if(n.next.data==d) {
			n.next=n.next.next;
			return head;
		}
		n=next;
	}
	return head;
}