자료구조-알고리즘/선형 자료구조

선형 자료구조: 연결리스트(Linked list)

vita12321 2023. 8. 20. 13:58
728x90
반응형

이 글에서는 선형 자료구조 중 하나인 연결리스트(linked list)에 대해 더 자세히 설명하고, 자바를 사용하여 연결리스트를 활용한 예제 코드를 작성해 보겠습니다. 먼저 연결리스트의 개념과 원리를 살펴본 뒤, 자바에서 연결리스트를 사용하는 방법과 기본 연산에 대해 알아보겠습니다. 마지막으로 실제 코드 예제를 통해 연결리스트의 활용을 연습해보겠습니다.

1. 연결리스트의 개념 및 원리

연결리스트(linked list)는 노드(node)라는 객체들이 서로 참조를 통해 연결된 구조로 구성되는 선형 자료구조입니다. 각 노드는 데이터를 저장하는 필드와 다음 노드를 참조하는 포인터(레퍼런스)를 가지고 있습니다. 배열과 달리 연결리스트는 연속된 메모리 공간에 저장되지 않고 동적으로 요소를 추가하거나 제거할 수 있습니다.

 

연결리스트의 종류에는 단일 연결리스트(singly linked list), 이중 연결리스트(doubly linked list), 원형 연결리스트(circular linked list) 등이 있습니다.

 

  • 연결리스트의 장점
  • 동적으로 크기 변경 가능: 노드 추가 및 삭제 시 메모리 관리가 효율적
  • 데이터 삽입 및 제거에 상대적으로 효율적

 

  • 연결리스트의 단점
  • 메모리 공간의 낭비: 다음 노드의 참조 정보를 저장하는 공간 필요
  • 인덱스를 이용한 빠른 데이터 접근 불가능: 노드를 순차적으로 방문해야 함

2. 자바에서의 연결리스트 사용법 및 주요 기능

 

자바에서 연결리스트를 구현하는 방식으로는 java.util.LinkedList 클래스를 사용하는 것이 있습니다. LinkedList 클래스는 다양한 자료형을 저장할 수 있도록 제네릭 형태로 제공됩니다.

 

  • 연결리스트 생성 및 초기화
LinkedList<Integer> linkedList = new LinkedList<>();

 

  • 연결리스트에 요소 추가
linkedList.add(1); // 마지막에 요소 추가

linkedList.addFirst(2); // 첫 번째 위치에 요소 추가

linkedList.addLast(3); // 마지막 위치에 요소 추가

linkedList.add(1, 4); // 인덱스 1 위치에 요소 4 추가

 

  • 연결리스트 요소 접근
int first = linkedList.getFirst(); // 첫 번째 요소 반환

int last = linkedList.getLast(); // 마지막 요소 반환

int elementAtIndex = linkedList.get(1); // 1번 인덱스의 요소 반환

 

  • 연결리스트에서 요소 제거
linkedList.removeFirst(); // 첫 번째 요소 제거

linkedList.removeLast(); // 마지막 요소 제거

linkedList.remove(1); // 인덱스 1 위치의 요소 제거

linkedList.remove(new Integer(2)); // 일치하는 첫 번째 요소 객체 제거

 

  • 연결리스트 크기 확인
int size = linkedList.size(); // 연결리스트 크기 반환

 

  • 반복자(Iterator)를 활용한 순회
Iterator<Integer> iterator = linkedList.iterator();

while (iterator.hasNext()) {

    int element = iterator.next();

    System.out.println(element);

}

3. 자바 연결리스트 예제: 기본 정수 연결리스트와 반복문 활용

 

다음 예제는 정수를 저장하는 연결리스트를 생성하고 초기화한 후, 반복문과 반복자를 이용해 연결리스트의 모든 요소를 출력하는 코드입니다.

import java.util.LinkedList;

import java.util.Iterator;

 

public class LinkedListExample {

 

    public static void main(String[] args) {

 

        LinkedList<Integer> linkedList = new LinkedList<>();

 

        for (int i = 0; i < 5; i++) {

            linkedList.add(i * 2 + 1); // 홀수 저장

        }

 

        // 반복자를 사용해서 전체 요소 출력

        Iterator<Integer> iterator = linkedList.iterator();

        while (iterator.hasNext()) {

            int number = iterator.next();

            System.out.println(number);

        }

    }

}

4. 결론

 

이 글에서는 선형 자료구조 중 하나인 연결리스트에 대해 더욱 자세히 살펴보았습니다. 배열과 비교했을 때, 연결리스트는 동적으로 크기 변경이 가능하고 데이터 삽입 및 삭제가 용이한 장점이 있지만, 메모리 공간의 낭비와 빠른 데이터 접근이 불가능한 단점이 있습니다. 또한, 직접 노드 클래스를 구현하여 연결리스트를 만들어 사용하는 방법도 있으나, 본 글에서는 자바의 LinkedList 클래스를 사용하는 방법에 집중하였습니다. 이러한 특성과 사용법을 숙지하여 상황에 맞게 적절한 자료구조를 선택하고 활용하는 능력을 키워 원활한 프로그래밍을 진행할 수 있길 바랍니다.

728x90
반응형