목록연결리스트 (3)
DNF LOVE
프로그래밍을 하다보면 각 특징에 맞게 효율적으로 데이터를 담는 자료구조가 존재한다.이 포스팅은 다양한 자료구조의 종류와 각 특징의 간단 정리를 하는 글이다.- 자료구조의 분류자료구조는 크게 두 분류로 나뉘어진다. 바로 선형구조와 비선형 구조이다. ■ 선형구조 : 선형 리스트(배열), 연결 리스트, 스택, 큐, 데크 ■ 비선형구조 : 트리, 그래프선형구조란? 자료를 구성하는 원소들은 순차적으로 나열시킨 형태를 의미한다. 어떤 연산들을 수행할 수 있느냐에 따라 세부적으로 나뉠 수 있다.비선형구조란? 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태를 의미한다.그림으로 보면 더 이해하기가 쉬울 것이다.선형구조는 아래와 같이 1부터 4까지 순차적으로 원소를 나열시키는 형태이며,비선형구조는 아래와 같이 하나..
* 앞서 리스트와 배열에 대해 알아보았는데 보통 컴퓨터 관련 학과에 진학하고 2학년 1학기쯤 되면 자료구조를 배우게 된다. 이 자료구조 수업시간에 가장 초기에 하는 구현은 연결리스트 구현이다. 연결리스트의 종류에는 크게 세 가지 정도가 있다. 단일 연결리스트, 원형 연결리스트, 양방향 연결리스트 이렇게 있다. 또 Head와 Tail의 유무 그리고 삽입 위치가 어디에 있냐에 따라 또 구현이 어느정도 달라진다. 연결리스트에서 새로운 노드를 추가할 때 리스트의 머리(head)부분과 꼬리(tail) 중 어디에 저장하여 노드를 연결하냐에 따라 구현이 달라진다는데 각 장단점을 서로 반대로 가지고 있다. 장점 단점 머리 포인터 변수 Tail이 불필요하다 저장된 순서가 유지되지 않는다. 꼬리 저장된 순서가 유지된다 포..
* 자료구조의 가장 간단한 부분인 리스트이다. 저번 학기에 도전했던 몇몇 회사 필테에 링크드리스트 구현 코드가 나왔었다. 기초가 부족했던 나는 폭망했다 ㅎ... 그래서 종강하면 바로 링크드리스트부터 공부해야겠구나 마음을 먹었다. 강하고 보름 내내 놀다가 이틀정도 공부했다. ㅎ 그래서 조금 허접하다. 암튼, 각색하고 리스트를 알기 전에 우선 가장 기본적인 배열을 알아보도록 하자. 배열의 가장 큰 특징은 인덱스를 가지고 있고, 초기에 배열의 크기가 정해진다. 그러고 인덱스 0부터 주어진 배열의 크기 -1 까지 데이터가 해당 인덱스에 따라 데이터를 여러개 가질 수 있는 자료구조이다. 그렇다면 리스트는 무엇인가? 리스트에는 크게 두 가지 종류가 있다. 바로 순차리스트와 연결 리스트다. 1. 순차 리스트 : 배열..