연결 리스트란?

<aside> 📖 배열과 다르게 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조이며, 각 노드는 포인터를 이용해 서로를 연결하여 접근한다.

</aside>

연결리스트 특징

장점

1. 배열과 다르게 요소의 수만큼 메모리를 할당받을 필요가 없다.
2. 배열과 다르게 공간을 추가로 할당받거나 나머지 데이터들의 위치를 이동시킬 필요가 없어서 삽입 및 삭제가 용이하다.

단점

1. 배열과 다르게 특정 인덱스의 위치에 O(1)에 접근하지 못하고 앞에서부터 순차적으로 요소를 탐색해야한다.
2. 각 노드가 데이터만 가지고 있는 것이 아닌, 포인터 변수의 공간도 추가적으로 필요하다.

코드로 보는 연결 리스트

노드 구현

class Node {
		int data; 
		Node pointer; 
	
		public Node(int data, Node pointer) {
			this.data = data;
			this.printer = pointer;
		}
}

1. 노드는 데이터와 다음 노드를 가리키는 변수를 갖고 있다.

연결리스트 구현

class LinkedList {
		Node head; 
		Node tail; 
	
		public LinkedList(Node head, Node tail) {
				head = null; 
				tail = null; 		
		}
}