이중 연결 리스트(뒤로 가기가 가능한 리스트)

이중 연결 리스트는 양방향 연결을 지원하는 리스트입니다. 각 노드가 다음 노드를 가리키는 포인터(rlink, right link)뿐만 아니라, 이전 노드를 가리키는 포인터(llink, left link)까지 함께 가지고 있습니다.

 이 차이로 특정 노드를 기준으로 앞뒤를 자유롭게 탐색할 수 있어 단순 연결 리스트에서는 비효율적이었던 '특정 노드 삭제'나 '역순 탐색' 같은 작업이 매우 간단하고 빨라집니다.

• 삽입 연산 : 새 노드를 중간에 삽입할 때, 새 노드와 그 앞뒤 노드 간의 관계를 모두 설정해야 합니다. 총 4개의 링크(포인터)를 조작하여 양방향 연결을 완성합니다.
• 삭제 연산 : 중간의 노드를 삭제할 때, 삭제할 노드의 앞 노드와 뒤 노드가 서로를 직접 가리키도록 두 개의 링크만 수정해주면 됩니다.

원형 이중 연결 리스트

원형 이중 연결 리스트는 이중 연결 리스트의 양 끝을 서로 연결하여 순환하는 구조로 만들어집니다. 이 구조의 핵심은 더미 노드(Dummy Node)의 존재입니다.

 더미 노드는 실제 데이터를 저장하지 않는 가짜 노드로, 리스트의 시작점과 끝점 역할을 합니다. 모든 연산은 이 더미 노드를 기준으로 이루어집니다.

• 더미 노드의 장점 : 리스트가 비어있을 때, 혹은 리스트의 맨 앞이나 맨 뒤에 데이터를 추가/삭제할 때 발생하는 까다로운 예외 상황을 처리할 필요가 없어집니다. 모든 삽입/삭제 연산이 '리스트 중간에서의 연산'과 동일한 로직으로 단순화되어 코드의 안정성과 가독성이 크게 향상됩니다.

순차 구조는 데이터에 빠르게 접근할 수 있다는 장점이 있으나, 중간에 데이터를 삽입하거나 삭제할 때마다 줄을 다시 맞추기 위해 많은 데이터를 옮겨야 하는 비효율적인 문제가 있습니다.이 문제를 해결하기 위해 '연결 자료구조'와 예시인 '연결 리스트'에 대해 글을 작성합니다.

연결 자료구조

연결 자료구조는 순차 자료구조와 반대의 아이디어에서 출발합니다. 데이터를 메모리상에 나란히 놓을 필요 없이, 흩어져 있는 데이터들을 주소(링크)를 이용해 논리적으로 연결하는 방식입니다.

각 데이터는 '다음 장소'에 대한 정보(다음 데이터의 메모리 주소)를 가지고 있습니다. 이 덕분에 중간에 새로운 데이터가 추가되어도 이전 데이터의 목적지만 바꿔주면 전체 흐름에 자연스럽게 끼어들 수 있습니다. 데이터를 일일이 옮길 필요가 없는 것입니다.

• 핵심 : 논리적 순서와 물리적 저장 순서가 다르다.
• 장점 : 데이터 삽입/삭제가 매우 빠르고, 필요한 만큼만 메모리를 사용하므로 유연하다.

연결 리스트의 기본 단위(노드)

연결 리스트는 '노드'라는 기본 단위들이 사슬처럼 연결된 구조입니다. 각각의 노드는 두 부분으로 구성됩니다.

1. 데이터 필드(Data Field) : 저장하고 싶은 실제 데이터(숫자, 문자 등)가 들어가는 공간입니다.
2. 링크 필드(Link Field) : 다음 노드가 어디에 있는지 그 '메모리 주소'를 저장하는 포인터 공간입니다. 이 링크가 바로 노드들을 연결하는 끈 역할을 합니다.

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

단순 연결 리스트는 기본적인 형태의 연결 리스트입니다. 각 노드가 하나의 링크 필드를 가져서, 다음 노드로만 이동할 수 있는 단방향 구조를 가집니다. 리스트의 가장 마지막 노드는 더 이상 가리킬 곳이 없으므로, 링크 필드에 NULL을 저장하여 리스트의 끝임을 표시합니다.

• 삽입 연산 : 데이터를 추가할 때, 이전 노드와 다음 노드 사이의 링크만 조정하면 됩니다. 새 노드를 만들고, 이전 노드의 링크가 새 노드를, 새 노드의 링크가 기존의 다음 노드를 가리키도록 연결을 바꿔주는 과정입니다.
• 삭제 연산 : 데이터를 삭제할 때도 같습니다. 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 직접 가리키도록 링크를 건너뛰게 만들어줍니다.

원형 연결 리스트 (Circular Linked List)

원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 NULL을 가리키는 대신, 리스트의 가장 첫 번째 노드를 가리키는 구조입니다. 이름처럼 노드들이 둥글게 원형으로 연결되어 있어 끝이 존재하지 않습니다.

이 구조는 마지막 노드에서 다시 첫 노드로 바로 이동해야 하는 작업이나, 리스트를 계속 순회해야 하는 경우에 매우 유용합니다.

연결 리스트는 순차 리스트의 단점을 극복하기 위해 등장한 중요한 자료구조입니다. 링크를 변경하는 것만으로 삽입과 삭제가 자유롭다는 강력한 장점 때문에, 다양한 알고리즘과 프로그램에서 핵심적인 역할을 담당합니다.

순차 자료구조와 선형 리스트

순차 자료구조 (Sequential Data Structure)

• 정의 : 데이터를 논리적 순서대로 메모리에 연속적으로 저장하는 구현 방식입니다.
• 핵심 특징 : 데이터의 논리적 순서와 메모리에 저장된 물리적 순서가 항상 일치합니다.
• 장점 : 인덱스를 통해 데이터에 빠르게 접근할 수 있습니다.
• 단점 : 삽입/삭제 시 데이터를 이동시켜야 하므로 비효율적일 수 있습니다. (↔ 연결 자료구조)

선형 리스트 (Linear List)

• 정의 : 데이터를 '나열'하는 가장 기본적인 자료구조로, 데이터들 간에 순서가 있는 리스트입니다.
• 구조 : 리스트의 각 데이터를 요소(element) 또는 노드(node)라고 부릅니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(논리적 연결)로 구성됩니다.
  • 헤드 노드(Head Node) : 리스트의 시작
  • 테일 노드(Tail Node) : 리스트의 끝

선형 리스트의 구현 방식

1. 선형 순차 리스트 (Linear Sequential List) : 배열을 사용하여 구현. 일반적으로 '선형 리스트'라고 부릅니다.
2. 선형 연결 리스트 (Linear Linked List) : 포인터를 사용하여 구현. 일반적으로 '연결 리스트'라고 부릅니다.

선형 리스트의 연산과 알고리즘 (배열 기반)

배열을 사용한 선형 리스트에서는 논리적 순서를 유지하기 위해 데이터의 물리적 이동이 필요합니다.

삽입 (Insertion) 연산

1. 삽입할 위치를 찾습니다.
2. 삽입할 위치부터 마지막 요소까지 모든 데이터를 한 칸씩 뒤로 이동시켜 빈자리를 만듭니다.
3. 만들어진 빈자리에 새로운 데이터를 삽입합니다.

• 이동 횟수 : 뒤에서부터 이동해야 데이터 덮어쓰기를 방지할 수 있습니다.

삭제 (Deletion) 연산

1. 삭제할 데이터를 찾습니다.
2. 삭제할 데이터의 다음 위치부터 마지막 요소까지 모든 데이터를 한 칸씩 앞으로 당겨 빈자리를 채웁니다.

• 이동 횟수 : 앞에서부터 이동해야 빈 공간을 효율적으로 채울 수 있습니다.

선형 리스트의 응용 및 구현

선형 리스트, 배열은 다양한 수학적 개념을 표현하는 데 사용됩니다.

행렬 (Matrix) 표현

• 행렬은 행과 열로 구성된 2차원 자료구조로, 2차원 배열을 사용해 자연스럽게 표현할 수 있습니다.
• 전치 행렬(Transpose Matrix) : 원래 행렬의 행과 열을 맞바꾼 행렬입니다.
• 희소 행렬(Sparse Matrix) : 대부분의 요소가 0인 행렬입니다.
  • 2차원 배열로 그대로 저장하면 0을 저장하기 위한 메모리 공간 낭비가 심합니다.
  • 해결책: 0이 아닌 요소만 <행, 열, 값>의 형태로 추출하여 2차원 배열에 저장하면 메모리를 크게 절약할 수 있습니다.

다항식 (Polynomial) 표현

• 다항식 P(x) = a_n * x^n + ... + a_1 * x^1 + a_0 * x^0을 선형 리스트로 표현할 수 있습니다.
• 1차원 배열 표현: 배열의 인덱스를 다항식의 '차수'로, 배열의 값을 '계수'로 사용하는 방식입니다.
  • A[i] = x^i 항의 계수
  • 단점: 3x^1000 + 4 와 같이 최고 차수는 높지만 항의 개수가 적은 '희소 다항식'의 경우, 중간의 사용하지 않는 공간 때문에 극심한 메모리 낭비가 발생합니다.
• 2차원 배열 표현 (희소 다항식): <계수, 차수> 쌍을 배열에 저장하여 메모리 낭비를 줄입니다.

웹 통신의 핵심, HTTP와 객체지향 프로그래밍의 원리

웹 서비스의 근간을 이루는 통신 규약인 HTTP의 원리를 중심으로 웹의 소통방법과 그 소통에 응답하는 프로그램은 어떤 원리로 만들어지는지에 대한 글을 작성합니다.

HTTP

HTTP(HyperText Transfer Protocol)는 웹 브라우저(클라이언트)와 웹 서버가 서로 데이터를 주고받기 위해 사용하는 기본 프로토콜, 즉 통신 규칙입니다. 모든 웹 통신은 클라이언트의 요청과 서버의 응답이라는 간단한 모델을 기반으로 합니다.

HTTP의 주요 특징 중 하나는 비연결성(Connectionless)입니다. 클라이언트가 서버에 요청을 보내고 응답을 받으면, 그 즉시 연결을 끊습니다. 이는 불특정 다수가 접속하는 웹 환경에서 서버 자원을 효율적으로 사용하여 더 많은 사용자의 요청을 처리할 수 있게 합니다.

또 다른 핵심 특징은 무상태성(Stateless)입니다. 비연결성의 특성으로 인해, 서버는 이전 요청에 대한 어떠한 정보도 기억하지 못합니다. 각 요청은 독립적인 트랜잭션으로 취급됩니다. 이러한 무상태성을 보완하고 사용자의 로그인 상태 등을 유지하기 위해 쿠키(Cookie)와 같은 기술이 사용됩니다.

HTTP 통신은 약속된 구조를 가진 메시지를 통해 이루어지며, 메시지는 요청과 응답의 두 가지 유형으로 나뉩니다.

HTTP 요청 메시지는 클라이언트가 서버에 특정 동작을 수행하도록 지시하는 메시지입니다. 주요 요청 메소드로는 자원 조회를 위한 GET, 새로운 자원 생성을 위한 POST, 기존 자원 수정을 위한 PUT, 자원 삭제를 위한 DELETE 등이 있습니다.

HTTP 응답 메시지는 서버가 클라이언트의 요청에 대한 처리 결과를 알려주는 메시지입니다. 응답은 상태 코드를 포함하는데, 200번대는 성공, 300번대는 리다이렉션, 400번대는 클라이언트 측 오류(예: 404 Not Found), 500번대는 서버 측 오류를 의미합니다.

웹 브라우저는 단순히 웹 페이지를 보여주는 것이 아닌 웹 통신의 클라이언트로서 복합적인 역할을 수행하는 소프트웨어입니다.

주요 역할은 크게 세 가지로 요약할 수 있습니다.

1. 사용자가 요청한 자원(웹 페이지, 이미지, 문서 등)을 서버에 요청합니다.
2. 서버로부터 전달받은 코드 형태의 자원(HTML, CSS, JavaScript)을 해석하여 시각적인 형태로 변환합니다.
3. 웹 페이지가 동적으로 상호작용할 수 있도록 실행 환경(런타임)을 제공합니다.

이러한 역할을 수행하기 위해 브라우저는 HTTP 규격에 맞춰 요청 메시지를 생성하고, 서버로부터 받은 응답 메시지를 분석하여 콘텐츠를 화면에 구성합니다. 이 과정에서 사용자 경험과 성능을 향상시키기 위해 캐싱과 쿠키 메커니즘을 사용합니다.

캐싱(Caching)은 한 번 방문했던 웹 페이지의 정적 자원(CSS, JavaScript, 이미지 등)을 사용자 컴퓨터에 임시로 저장하는 기술입니다. 이를 통해 동일한 페이지를 다시 방문할 때 서버에 모든 자원을 재요청하는 대신, 저장된 자원을 바로 불러와 페이지 로딩 속도를 크게 향상시키고 데이터 사용량을 줄입니다.

쿠키(Cookie)는 서버가 사용자의 상태 정보를 클라이언트 PC에 저장하기 위한 작은 텍스트 파일입니다. HTTP 통신은 기본적으로 상태를 유지하지 않으므로, 쿠키를 통해 로그인 정보 유지, '오늘 하루 이 창을 보지 않기'와 같은 사용자 설정을 기억할 수 있습니다.

웹 브라우저의 내부 구조와 렌더링 과정

웹 브라우저가 서버로부터 받은 코드를 화면에 나타내기 전에, 내부에서 렌더링 과정이 진행됩니다. 이 과정의 핵심은 렌더링 엔진이며

렌더링 엔진의 동작은 아래와 같은 주요 단계로 이루어집니다.

1. HTML 파싱과 DOM 트리 생성 : 서버로부터 받은 HTML 문서를 파싱(해석)하여, 각 태그를 객체로 변환한 문서 객체 모델(DOM) 트리를 구축합니다.
2. CSS 파싱과 렌더 트리 생성 : CSS 파일을 파싱하여 스타일 정보를 얻고, 이를 DOM 트리와 결합하여 화면에 실제로 표시될 요소들로만 구성된 렌더 트리를 생성합니다.
3. 레이아웃(Layout) : 렌더 트리의 각 노드(요소)가 화면의 어느 위치에 어떤 크기로 표시될지를 정확하게 계산합니다.
4. 페인팅(Painting ): 레이아웃 계산이 완료된 렌더 트리의 각 노드를 화면에 실제 픽셀로 그려냅니다.

최신 브라우저는 사용자 경험을 위해 모든 HTML을 다 읽을 때까지 기다리지 않고, 데이터를 받는 대로 순차적으로 파싱하고 렌더링하여 화면의 레이아웃부터 점차 세부 항목이 나타나는 형태로 콘텐츠를 보여줍니다.