[알고리즘][코딩 인터뷰 완전 분석 정리] 02 연결리스트

연결리스트 개요 

• 차례로 연결된 노드를 표현해주는 자료구조.
• 다음 주소값을 가지고 있는 데이터 구조.
• 단방향/양방향 연결리스트 

 

 

• 속도가 느릴 순 있다. K번째 원소를 찾고 싶다면 처음부터 K번 루프를 돌아야함.
• 장점은 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다.
• 길이가 정해지지 않은 데이터를 핸들링할때는 OK
• (cf . 배열은 크기가 정해져 있다.)

 

 

연결리스트 만들기

• LinkedList 구조를 사용하지 않고 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법.

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;    
    }
}

 

위의 코드는 이전 head를 계속 가리키고 있을 수도 있다. 그렇기 때문에 해당 클래스안에 head Node 변수를 단 하나만 정의해 놓을으로써 위의 문제점을 완전히 해결할 수 있다. 

 

public class LinkedList {
	Node header;
    static class Node{
        int data;
        Node next  = null;        
        public Node(){
        }
        public Node(int data) {
            this.data = data;
        }
    }

    LinkedList(){
        header = new Node();
    }
    
     void append(int d){
        Node end = new Node();
        end.data = d;
        Node n = header;
        while (n.next != null){
            n = n.next;
        }
        n.next = end;
    }
 }