Chatper 8

Generic Programming with LinkedList & Stack

LinkedList Template

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <typename T>
class Node {
public:
T element ;
Node * next ;
Node() {
next = NULL ;
}
Node(T element) {
this->element = element ;
next = NULL ;
}
} ;

template <typename T>
class LinkedList {
Node<T> * head , * tail ;
int size ;
public:
LinkedList() ;
void addFirst(T element) ; //첫번째 원소로 추가
void addLast(T element) ; //마지막 원소로 추가
T getFirst() ; //첫번째 원소 반환
T getLast() ; //마지막 원소 반환
T removeFirst() ; //첫번째 원소 제거
T removeLast() ; //마지막 원소 제거
void add(T element) ; //원소 추가
void add(int index , T element) ; //해당 위치에 원소 추가
void clear() ; //전체 삭제
T get(int index) ; //특정 위치 원소 반환
bool isEmpty() ; // 비어있는지 검사
int getSize() ; //크기 반환

//bool contains(T element) ; //T가 포함되어 있는지 검사
//int indexOf(T element) ; //T의 원소의 위치 반환
//int lastIndexOf(T element); //T의 마지막 원소 위치 반환
//void remove(T element); //T 원소 검색해서 제거
//T removeAt(int index) ; //특정 위치의 원소 제거
//T set(int index , T element) ; //특정 위치의 원소 교체
};

template<typename T>
LinkedList<T>::LinkedList() {
head = tail = NULL ;
size = 0 ;
}

template <typename T>
void LinkedList<T>::addLast(T element) {
if( tail == NULL) {
head = tail = new Node<T>(element) ;
} else {
tail->next = new Node<T>(element) ;
tail = tail->next ;
}
size++ ;
}

template <typename T>
void LinkedList<T>::addFirst(T element) {
if( head == NULL) {
head = tail = new Node<T>(element) ;
} else {
Node<T> * temp = new Node<T>(element) ;
temp->next = head;
head = temp ;
}
size++ ;
}

template <typename T>
T LinkedList<T>::getFirst() {
if( size > 0 ) {
return head->element ;
}
return NULL ;
}

template <typename T>
T LinkedList<T>::getLast() {
if( size > 0 ) {
return tail->element ;
}
return NULL ;
}


template <typename T>
T LinkedList<T>::removeFirst() {
if( size > 0) {
Node<T> * t = head;
head = head->next ;
if( head == NULL) tail = NULL ;
size -- ;
T element = t->element ;
delete t ;
return element ;
}
return NULL ;
}

template <typename T>
T LinkedList<T>::removeLast() {
if(size == 1 ) {
Node<T> * t = head ;
head = tail = NULL ;
size = 0 ;
T element = t->element ;
delete t ;
return element ;
} else if( size > 1 ) {
Node<T> * current = head ;
for(int i = 0 ; i < size -2 ; i++)
current = current->next ;
Node<T> * t = tail ;
tail = current ;
tail->next = NULL ;
size -- ;
T element = t->element ;
delete t ;
return element ;
}
return NULL ;
}

template <typename T>
void LinkedList<T>::add(T element) {
addLast(element) ;
}
template <typename T>
void LinkedList<T>::add(int index , T element) {
if( index == 0 ) addLast(element) ;
else if(index >= size) addLast(element) ;
else {
Node<T> * current = head ;
for(int i = 1 ; i < index ; i++)
current = current->next ;
Node<T> * t = current->next;
current->next = new Node<T>(element) ;
(current->next)->next = t;
size ++ ;
}
}

template <typename T>
void LinkedList<T>::clear() {
while(head != NULL) {
Node<T> * t = head;
head = head->next ;
delete t ;
}
tail = NULL ;
}

template <typename T>
T LinkedList<T>::get(int index) {
Node<T> * current = head ;
for(int i = 0 ; i < index ; i++)
current = current->next ;
return current->element ;
}

template <typename T>
bool LinkedList<T>::isEmpty() {
return head == NULL ;
}

template <typename T>
int LinkedList<T>::getSize() {
return size ;
}
#endif

7회차 파워포인트 자료

7회차 string 클래스와 템플릿입니다.


다운로드하기

6회차 상속과 연산자 오버로딩(후반부)

6회차 상속과 연산자 오버로딩(후반부) 강의입니다.

6회차 다형성과 상속 (전반부)

다형성과 상속 전반부 강의입니다.

1~6회차까지의 파워포인트 강의 자료

아래의 링크를 클릭하면 됩니다. 문서는 아도브 아크로뱃으로 되어 있습니다.


여기를 클릭

5회차 상속과 복사 생성자

복사 생성자와 상속에 대하여 살펴봅니다.