[PCCP] 자료구조 - 링크드리스트

1. 이론

 

 

2. 프로그램 언어별 문법

<C언어>

#include <stdio>
#include <stdlib.h>

/* 1차원 동적배열 선언 및 초기화 */
int* arr1 = (int*)malloc(sizeof(int) * 5);
if (arr1 == NULL){
    printf("[error]: malloc error\n");
}
    
/* 2차원 동적 배열 선언 및 초기화 */


// 동적배열 해제
free(arr1);

 

<C++>

(단방향 리스트: forward_list)

#include <forward_list>

// 단방향 리스트 선언 및 초기화
forward_list<int> list1;
forward_list<int> list2(7); // 크기가 7
forward_list<int> list3(10, 5); // 크기가 10, 초기값은 5
forward_list<int> list4 = {1,2,3,4,5};

// 삽입
list.push_front(val);
list.insert_after(반복자, val);

// 삭제
list.pop_front();
list_erase_after(반복자); // 반복자 위치 다음 원소 삭제
list_erase_after(시작반복자, 끝반복자);

// 변경

// 조회
for (forward_list<int>::iterator it = list.begin(); it != list.end(); it++)
    std::cout << *it << std::endl;

 

(양방향 리스트:list)

#include <list>

// 양방향 리스트 생성 
list<int> li1;  
 
// 삽입 
li.push_front(val);
li.push_back(val);
li.insert(반복자, val);

// 삭제
li.pop_front();
li.pop_back();

// 변경


// 조회
li.front();
li.back();

for (list::<int>::iterator it = a.begin(); it != li.end(); it++)
    std::cout << *it << std::endl;

// 크기
li.size();

// 비었는지 확인
li.empty();

 

<Java>

- ArrayList: 크기가 동적으로 변경되는 배열

// 링크드리스트 선언 및 초기화
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>(list1);
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 4, 5, 3));


// 삽입(맨 뒤)
list.add(val);

// 삭제
list.remove(index);      // O(N)

// 값 확인
list.get(index);

// 데이터 개수
list.size();

// 남은 데이터 여부
list.isEmpty();

// 정렬(오름차순)
Collections.sort(list);

 

<Python>

 

 

3. 추천 문제(Programmers)

-