[Algorithm] LinkedList 1 (02/24)

박세윤·2023년 2월 24일

Java algorithm

Algorithm

목록 보기

10/24

📖 LinkedList

📌 연결 리스트

✅ 특성

자료의 논리적 순서와 메모리 상 물리적 순서가 일치 X
개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다.
링크를 통해 원소에 접근 => 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업 필요 X
자료구조 크기 동적 조정 가능 => 메모리의 효율적 사용 가능

✅ 구성 요소

노드
- 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위
- 구성 요소
  
  1) 데이터 필드
  원소의 값을 저장하는 자료구조
  저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용
  
  2) 링크 필드
  다음 노드의 주소 저장
헤드
- 리스트의 처음 노드를 가리키는 레퍼런스

📌 단순 연결 리스트 (Singly Linked List)

✅ 연결 구조

노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조
헤드가 가장 앞의 노드를 가리키고 링크 필드가 연속적으로 다음 노드를 가리킴
최종적으로 NULL을 가리키는 노드가 리스트의 마지막 노드

✅ 과정

'A', 'C', 'D'를 원소로 갖고 있는 리스트의 두 번째에 'B' 노드를 삽입할 때

메모리를 할당하여 새 노드 new 생성

새 노드 new의 데이터 필드에 'B' 저장

삽입될 위치의 바로 앞에 위치한 노드의 링크 필드를 new에 복사

new의 주소를 앞 노드의 링크 필드에 저장

✅ LinkedList 연산

AddFirst
AddLast
AddAfter
RemoveFirst
RemoveLast
RemoveAfter
PrintList
getNode

✅ 첫 번째 노드로 삽입하는 알고리즘

addtoFirst(L, i) { // 리스트 포인터 L, 원소 i
	new <= createNode(); // 새 노드 생성
    new.data = i;
    new.link = L;
    L = new;
}

✅ 가운데 노드로 삽입하는 알고리즘

노드 pre의 다음 위치에 노드 삽입

add(L, pre, i) // 리스트 L, 노드 pre, 원소 i
	new <- createNode(); // 새로운 노드 생성
    new.data = i;
    
    if(L == NULL) {
    	L = new;
        new.link = NULL;
    }
    else {
    	new.link = pre.link;
        pre.link = new;
    }

✅ 마지막 노드로 삽입하는 알고리즘

addtoLast(L, i) // 리스트 L, 원소 i
	new <- createNode(); // 새로운 노드 생성
    new.data = i;
    new.link = NULL;
    
    if(L == NULL) { // 빈 리스트일 때, 최초 노드 추가
    	L = new;
        return;
    }
    temp = L; // 노드 링크 이용하여 리스트 순회
    while(temp.link != NULL) { // 마지막 노드 찾을 때까지 이동
    	temp = temp.link;
    }
    temp.link = new; // 마지막 노드 추가

✅ 'A', 'B', 'C', 'D' 리스트의 'B' 노드를 삭제할 때

삭제할 노드의 앞 노드(선행노드) 탐색

삭제할 노드의 링크 필드를 선행 노드의 링크 필드에 복사

✅ 노드를 삭제하는 알고리즘

노드 pre의 다음 위치에 있는 노드 삭제

delete(L, pre) { // 리스트 L, 노드 pre
	if(L == NULL) error;
    else {
    	targe =pre.link; // 삭제 노드 지정
        if(target == NULL) return;
        pre.link = target.link;
    }
    freeNode(target) // 할당된 메모리 반납
}