연결 리스트에서는 데이터를 노드(Node) 단위로 저장합니다. 노드에는 데이터와 자기 자신의 노드와 연결되어 있는 다른 노드(들)의 주소 값을 저장하고 있습니다. 연결 리스트에서 맨 첫번째 노드를 Head라고 지칭하고, 마지막에 있는 노드를 Tail이라고 지칭합니다.
배열과의 차이점은, 배열은 연관된 데이터들을 순차적으로 적재하지만, 연결 리스트에서는 각각 따로 저장하고 서로의 주소를 저장하고 있으므로, 주소를 참조해서 다음 데이터를 접근합니다.

(단일 연결 리스트: https://www.fun-coding.org/00_Images/linkedlist.png)
주로 연결 리스트는 C언어에서 사용 되는 데이터 구조이지만, 파이썬에서도 구현 가능합니다.

(C언어로 이중 연결 리스트 구현했던 코드)

typedef struct Day
{
	struct Day *llink;
	char DofW[10];
	struct Day *rlink;
}day;

typedef struct List
{
	day *rlink;
}linked_list;
linked_list *createList()
{
	linked_list *a;
	a = (linked_list *)malloc(sizeof(linked_list));
	return a;
}
day *addNode(char *p)
{
	day *a;
	a = (day *)malloc(sizeof(day));
	strcpy(a->DofW, p);

	return a;
}
void addLeftLink(day *ptmp, day *arr)
{
	arr->llink = ptmp;
}
void addMon(day *mon, linked_list *first)
{
	day *tmp = first->rlink; // tmp == arr[0]
	tmp->llink = mon;

	mon->rlink = first->rlink;
	first->rlink = mon;
	mon->llink = NULL;
}
void printList(linked_list *first)
{
	day *a = first->rlink;

	if (first->rlink != NULL)
	{
		printf("%s\n", a->DofW);
		while (a->rlink != NULL)
		{
			a = a->rlink;
			printf("%s\n", a->DofW);
		}
	}
}
void printListRev(day *arr)
{
	day *a = arr;

	while(a->rlink != NULL)
	{
		a = a->rlink;
	}
	printf("%s\n", a->DofW);
	while (a->llink != NULL)
	{
		a = a->llink;
		printf("%s\n", a->DofW);
	}

}
void deleteFirstNode(linked_list *first)
{
	day *del = first->rlink, *a = first->rlink;

	a = a->rlink;
	a->llink = NULL;
	first->rlink = a;

	free(del);
}
int main()
{
	day *arr, *mon, *ptmp;
	linked_list *first;
	char tmp[4][10];

	first = createList();

	strcpy(tmp[0], "화");
	strcpy(tmp[1], "수");
	strcpy(tmp[2], "목");
	strcpy(tmp[3], "월");

	arr = addNode(tmp[0]);
	first->rlink = arr;
	arr->llink = NULL;
	
	ptmp = arr;
	arr->rlink = addNode(tmp[1]);
	arr = arr->rlink;
	addLeftLink(ptmp, arr);
		
	ptmp = arr;
	arr->rlink = addNode(tmp[2]);
	arr = arr->rlink;
	arr->rlink = NULL;
	addLeftLink(ptmp, arr);

	printList(first);
		
	mon = addNode(tmp[3]);
	addMon(mon, first);

	printf("\n");
	printList(first);

	printf("\n");
	printListRev(arr);

	deleteFirstNode(first);

	printf("\n");
	printList(first);
	
	printf("\n");
	printListRev(arr);

	return 0;
}

단일 연결 리스트

단일 연결 리스트는 노드가 한 방향으로만 접근 할 수 있는 연결 리스트입니다. 즉, 노드가 자신의 다음 노드의 주소를 가지고 있어서 다음 노드를 접근 할 수 있지만, 자신의 이전 노드의 주소는 갖고 있지 않아서 이전 노드는 접근하지 못하는것 입니다.

노드(Node):

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

노드에서 data는 저장할 데이터를 가지고 있으며, next에는 다음 노드의 주소를 저장합니다.

연결 리스트 구현하기:

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
    
    def add(self, data): # 제일 마지막에 새로운 노드 추가하기
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def desc(self): # Head부터 순회해서 모든 노드의 데이터 출력하기
        node = self.head
        while node:
            print (node.data)
            node = node.next

    def delete(self, data): # 특정 data 값을 가진 노드 삭제하기
        if self.head == '':
            print ('해당 값을 가진 노드가 없습니다.')
            return
        if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
            temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
            self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
            del temp
        else:
            node = self.head
            while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next       
                    del temp                         
                    pass                             
                else:
                    node = node.next
                    
    def search_node(self, data): # 특정 data 값을 가진 노드 찾기
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

여기서 가장 눈여겨볼 메서드는 delete(self, data) 메서드 입니다. 해당 메서드는 연결 리스트에서 특정 값을 가진 노드를 삭제하는 것인데요, 이때 고려해야될 것들이 있습니다.

첫번째는, 연결 리스트에서의 노드를 삭제하면, 삭제한 노드 기준으로 이전 노드들과 이후의 노드들이 연결이 끊어지기 때문에, 연결이 끊어지지 않도록 해야합니다. 그렇게 하기 위해서는 삭제한 노드 직전 노드의 next가 삭제한 노드의 next를 가르키고 있도록 하면 됩니다.즉, A->B->C로 연결된 리스트에서 B를 삭제하면, A->C가 되도록 노드 A의 next가 노드 C를 가르키도록 하는데, 이때 노드 C의 주소는 노드 B의 next에 저장되어 있는 주소 입니다.

두번째로 고려할 것은, 삭제하는 데이터가 Head일떄 입니다. 이때는 삭제후, Head를 갱신시켜줘야 합니다. A->B->C로 연결되어 있고, 노드 A가 Head이며 노드 A를 삭제할때는 Head가 노드 B가 되도록 갱신시켜줘야 하는데, 노드 B의 주소는 노드 A의 next에 있는 주소입니다.
이때, 단일 리스트에서는 이전 노드로 이동을 못하기 때문에 삭제할 값을 찾을때 현재 노드의 data를 보는 것이 아니라, 현재 노드가 가르키고 있는 다음 노드의 data 값을 기준으로 탐색합니다.

				if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next       
                    del temp                         
                    pass                             
                else:
                    node = node.next

이중 연결 리스트

이중 연결 리스트는 단일 연결 리스트에서 자신의 이전 노드를 접근하지 못하는 문제점을 해결한 데이터 구조입니다.

(https://www.fun-coding.org/00_Images/doublelinkedlist.png)

노드(Node):

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next

단일 연결 리스트에서의 노드와 마찬가지로, data는 데이터를 저장하고 next에는 다음 노드의 주소를 저장합니다. 다만, 이중 연결 리스트에서는 이전 노드의 주소를 저장하는 prev 변수가 추가 됐습니다.

이중 연결 리스트:

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    
    def insert_before(self, data, before_data): # 특정 값 이전에 노드 추가
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.next = node
            return True
    def insert_after(self, data, search_data): # 특정 값 이후에 노드 추가
        node = self.tail 
        
        while True:
            if node.data == search_data:
                break
            node = node.prev
        new = Node(data)
        
        if node.next == None:
            self.tail = new
        
        new.next = node.next
        new.prev = node
        node.next = new

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

이중 연결 리스트에서 노드를 추가 할때는 next와 prev 둘 다 갱신을 해줘야 하며, 노드가 맨 처음 또는 맨 마지막에 추가됨에 따라서 각각 Head와 Tail을 갱신시켜줘야 되는 것을 유의해야 합니다.

결과 확인하기:

double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)

double_linked_list.insert_before(-1, 0) # 0(첫번째 노드) 이전에 -1 추가하기
double_linked_list.insert_before(8.5, 9) # 9 이전에 8.5 추가하기
double_linked_list.insert_after(2.5, 2) # 2 이후에 2.5 추가하기
double_linked_list.insert_after(9.5, 9) # 9(마지막 노드) 이후에 9.5 추가하기

double_linked_list.desc()

결과:
-1
0
1
1.5
2
2.5
3
4
5
6
7
8
8.5
9
9.5