[자료구조] 연결리스트 Linked List

연결리스트는 배열과 리스트의 단점을 보완한 구조이다.

리스트 데이터 삽입

배열과 리스트의 경우 중간에 특정 데이터가 삽입되어야 한다면 위와같이 기존의 데이터들을 한칸씩 뒤로 이동해 주어야 한다. 삭제를 할 땐 빈공간을 채우기 위해 한칸씩 앞으로 이동해 주어야 한다. 뿐만 아니라 데이터가 꽉 차있는 상태에서 추가하고자 할 때는 메모리에 새로운 공간을 기존의 크기만큼 추가로 할당 하여 리스트의 맨 마지막에 새로운 데이터를 추가해야 하는 번거로움이 생긴다. 이렇듯 메모리관리에 어려움이 생길 수 있다는 것이 가장 큰 단점인데 이 부분을 보완한 자료구조가 연결리스트라고 할 수 있다.

연결리스트

• 선형 동적자료구조
• 인덱스 없음
• 데이터필드와 하나이상의 링크필드로 구성된 노드를 갖는다.
• 링크 : 다른 노드를 가리키는 주소를 갖는다.

노드 구조

연결리스트 종류

• 단순연결리스트 
  : 한 방향으로만 연결되는 리스트. 각 노드는 다음 노드의 주소를 가리키며 tail 노드는 마지막 노드라는 것을 나타내기 위해 링크에 none 값을 갖고있다.

• 원형연결리스트
  : tail노드에 head노드의 주소를 넣어서 head노드를 가리킨다. 

• 이중연결리스트
  : 각 노드들이 두 개의 링크를 갖는 구조. 이전노드를 가리키는 previous link와 다음노드를 가리키는 next link. 맨 첫 번째 노드의 previous link 는 첫 번째 노드를 가리키는 head point 를 가리킨다.

import java.util.Comparator;

public class LinkedList<E> {
	
    class Node<E> {
    	private E data;
        private Node<E> next;   //포인터
        
        Node(E data, Node<E> next) {
        	this.data = data;
            	this.next = next;  
        }
    }
    private Node<E> head;	//머리노드
    private Node<E> crnt;	//현재 선택한 노드