선형자료구조 - 연결리스트(LinkedList)

LinkedList.

선형으로 자료를 관리, 자료가 추가 될 때마다 메모리를 할당받고,
자료는 링크로 연결되어 물리적 위치와 논리적 위치가 다를 수 있음.

연결리스트의 각 요소는 다음 주소값을 가리키는 주소값을 가짐
물리적인 메모리가 떨어져 있어도 논리적으로는 앞뒤 순서가 있음.
같은 List 인터페이스를 구현한 ArrayList에 비해 중간에 자료를 삽입하고 제거하는데
시간이 적게 걸림
크기를 동적으로 증가할 수 있음
연결리스트의 각 요소는 요소의 자료와 다음 주소를 저장하는 부분으로 구현
또한 스택이나 큐에서 다양하게 활용할 수 있음

 

배열과 연결리스트의 차이점.

자료의 변동(수정, 삭제) 등이 많다면 연결리스트 사용
거의 없다면 배열을 사용하는게 좋다.

연결리트스 데이터 추가.

• 연결 리스트 가장 앞에 데이터 추가
  추가할 데이터를 담을 노드를 생성
  head를 추가 데이터로 변경
  추가 데이터의 next를 이전 head의 데이터로 연결

• 연결 리스트 중간에 데이터 추가
  추가할 데이터를 담을 노드 생성
  head로 부터 데이터 추가 위치 직전 노드까지 순회
  직전 노드.next -> new data / new data.next -> 다음 노드.data 

• 연결 리스트 끝에 데이터 추가
  추가할 데이터를 담을 노드 생성
  hea부터 마지막 노드까지 순회
  마지막 노드의 next 에 new data / next -> null (단방향)

 

연결리트스 데이터 삭제.

• 가장 앞의 데이터 삭제
  삭제 대상 노드 지정
  삭제 대상 노드의 next -> head로 변경
  노드 삭제

• 중간 데이터 삭제
  head로부터 삭제 대상 노드까지 순회 및 해당 노드 지정
  삭제 대상 이전 / 이후 노드의 링크 연결 작업 (이전 Node.next -> 이후 Node.data)
  
  

• 가장 끝 데이터 삭제
  head로부터 가장 끝까지 순회
  끝 노드 삭제
  삭제 이전 노드의 링크 처리 (단방향이면 null, 원형이면 head)

LikedList 주요 메서드

package day013;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListMethodTest {
    public static void main(String[] args) {
        // LinkedList 초기의 크기를 미리 생성할수는 없음
        LinkedList<Integer> list = new LinkedList<>();

        // add
        list.addFirst(1); // 가장 앞 head 데이터 추가
        list.addLast(2); // tail 데이터 추가
        list.add(1, 10); // 중간 데이터 추가
        list.add(20); // index 생략 시 마지막에 추가
        list.add(30); // index 생략 시 마지막에 추가
        System.out.println(list); // [1, 10, 2, 20, 30]

        // remove
        System.out.println(list.removeFirst()); // head 삭제 1
        System.out.println(list.removeLast()); // tail 삭제 30
        System.out.println(list.remove()); // 0번째 삭제 10
        System.out.println(list.remove(1)); // 중간 삭제  20
        System.out.println(list); // [2]

        // size
        System.out.println(list.size()); // 1

        // 출력

        LinkedList<Integer> list1 = new LinkedList<Integer>(Arrays.asList(1,2,3));

        System.out.println(list1.get(0));//0번째 index 출력

        for(Integer i : list1) { //향상된 for 문을 통한 전체출력
            System.out.println(i);
        }

        Iterator<Integer> iter = list1.iterator(); // Iterator 선언
        while(iter.hasNext()){ // 다음값이 있는지 체크
            System.out.println(iter.next()); //값 출력
        }
    }
}

 

 

---

LikedList 메서드 참고 출처 : https://coding-factory.tistory.com/552