danh sách liên kết đơn

By Admin 03/06/2024 0

Bài ghi chép được sự được chấp nhận của người sáng tác Khiêm Lê

Bạn đang xem: danh sách liên kết đơn

Danh sách links đơn (Single Linked List) là một trong cấu tạo tài liệu động, nó là một trong list nhưng mà từng thành phần đều links với thành phần đích thị sau nó nhập list. Mỗi thành phần (được gọi là một trong node hoặc nút) nhập danh sách liên kết đơn là một trong cấu tạo sở hữu nhị trở nên phần:

  • Thành phần dữ liệu: lưu vấn đề về bạn dạng thân thiện thành phần cơ.
  • Thành phần liên kết: lưu vị trí thành phần đứng sau nhập list, nếu như thành phần này là thành phần ở đầu cuối thì bộ phận này bởi vì NULL.

Tham khảo thêm: việc thực hiện lập trình sẵn c++ lương bổng cao bên trên Topdev

Danh sách links đơn nhập C++
Minh họa danh sách liên kết đơn

Đặc điểm của danh sách liên kết đơn

Do danh sách liên kết đơn là một trong cấu tạo tài liệu động, được tạo thành nhờ việc cấp phép động nên nó sở hữu một trong những Đặc điểm sau đây:

  • Được cấp phép bộ lưu trữ Khi chạy chương trình
  • Có thể thay cho thay đổi độ cao thấp qua loa việc tăng, xóa phần tử
  • Kích thước tối nhiều tùy theo bộ lưu trữ khả dụng của RAM
  • Các thành phần được tàng trữ tình cờ (không liên tiếp) nhập RAM

Và bởi tính links của thành phần đầu và thành phần đứng sau nó nhập danh sách liên kết đơn, nó sở hữu những Đặc điểm sau:

  • Chỉ cần thiết cầm được thành phần đầu và cuối là rất có thể vận hành được danh sách
  • Truy cập cho tới thành phần tình cờ cần duyệt từ trên đầu cho tới địa điểm đó
  • Chỉ rất có thể thám thính tìm kiếm tuyến tính 1 phần tử

Cài đặt điều danh sách liên kết đơn

Trước Khi cút nhập thiết đặt danh sách liên kết đơn, hãy chắc chắn rằng rằng chúng ta vẫn nắm rõ phần con cái trỏ và cấp phép động nhập C++. Do danh sách liên kết đơn là một trong cấu tạo tài liệu động, nếu khách hàng ko nắm rõ con cái trỏ và cấp phép động tiếp tục cực kỳ khó khăn nhằm chúng ta nắm chắc nội dung bài viết này. Nếu chúng ta cảm nhận thấy ko mạnh mẽ và tự tin, hãy dành riêng không nhiều thời hạn nhằm xem bài ghi chép này của bản thân. Còn lúc này thì chính thức thôi!

Tạo node

Danh sách links đơn được tạo nên trở nên từ không ít node, vì thế, tất cả chúng ta tiếp tục nằm trong cút kể từ node trước. Một node bao gồm nhị bộ phận là bộ phận tài liệu và bộ phận links. Thành phần tài liệu rất có thể là loại tài liệu đã có sẵn hoặc chúng ta tự động khái niệm (struct hoặc class…), nhập nội dung bài viết này nhằm giản dị bản thân tiếp tục dùng loại int cho tới phần tài liệu. Thành phần links là vị trí đương nhiên được xem là con cái trỏ, con cái trỏ này trỏ cho tới node tiếp theo sau, vì thế, con cái trỏ này là con cái trỏ trỏ vào trong 1 node.

struct Node
{
	int data;
	Node* next;
};

Để tạo nên một node mới nhất, tớ triển khai cấp phép động cho tới node mới nhất, khởi tạo nên độ quý hiếm lúc đầu và trả về vị trí của node vừa được cấp phép.

Node* CreateNode(int init_data)
{
	Node* node = new Node;
	node->data = init_data;
	node->next = NULL;      // node một vừa hai phải tạo nên ko thêm vô list nên ko links với thành phần nào là cả nên phần links gán bởi vì NULL
	return node;
}

Tạo danh sách liên kết đơn

Ta vẫn dành được bộ phận tạo thành danh sách liên kết đơn là node, tiếp theo sau tất cả chúng ta cần thiết vận hành bọn chúng bằng phương pháp hiểu rằng thành phần đầu và cuối. Vì từng thành phần đều links với thành phần tiếp vậy nên miêu tả chỉ nên biết thành phần đầu và cuối là rất có thể vận hành được list này. Vậy giản dị tớ cần thiết tạo nên một cấu tạo tàng trữ vị trí thành phần đầu (head) và thành phần cuối (hay thành phần đuôi tail).

struct LinkedList
{
	Node* head;
	Node* tail;
};

Khi mới nhất tạo nên list, list tiếp tục không tồn tại thành phần nào là, vì thế head và tail ko trỏ nhập đâu cả, tớ tiếp tục gán bọn chúng bởi vì NULL. Ta xây đắp hàm tạo nên list như sau:

void CreateList(LinkedList& l)
{
	l.head = NULL;
	l.tail = NULL;
}

Bây giờ sẽ tạo một list, tớ thực hiện như sau:

LinkedList list;
CreateList(list); // Gán head và tail bởi vì NULL

Thêm thành phần nhập danh sách

Thêm nhập đầu

Để tăng node nhập đầu list, thứ nhất tớ cần thiết thám thính tra coi list cơ sở hữu trống rỗng hay là không, nếu như list trống rỗng, tớ chỉ việc gán head và tail của list bởi vì node cơ. trái lại nếu như list ko trống rỗng, tớ triển khai trỏ bộ phận links nhập head, tiếp sau đó gán lại head bởi vì node mới nhất.

void AddHead(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		node->next = l.head;
		l.head = node;
	}
}

Danh sách links đơn nhập C++
Thêm thành phần nhập đầu danh sách liên kết đơn

Như nhập hình bên trên, tất cả chúng ta tăng node sở hữu data bởi vì 0 nhập list. Ta triển khai trỏ next của node cơ nhập head của list (chính là node thứ nhất của list sở hữu data bởi vì 1), tiếp sau đó tớ trỏ head nhập node sở hữu data 0 vừa mới được tăng. Vậy là thành phần này đã nằm tại đầu list rồi.

Thêm nhập cuối

Tương tự động, nhằm tăng node vào thời gian cuối list, thứ nhất tớ đánh giá coi list trống rỗng hay là không, trống rỗng thì gán head và tail đều bởi vì node mới nhất. Nếu ko trống rỗng, tớ triển khai trỏ tail->next nhập node mới nhất, tiếp sau đó gán lại tail bởi vì node mới nhất (vì lúc này node mới nhất tăng đó là tail).

void AddTail(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		l.tail->next = node;
		l.tail = node;
	}
}

Danh sách links đơn nhập C++
Thêm thành phần vào thời gian cuối danh sách liên kết đơn

Xem thêm: hôm nay là thứ bảy

Trong hình bên trên, tất cả chúng ta triển khai tăng node sở hữu data bởi vì 6 nhập list. Tail thời điểm hiện tại là node sở hữu data 5, triển khai gán tail->next bởi vì node mới nhất nhằm nối tăng nó nhập đuôi list, thời điểm hiện tại node mới nhất trở nên thành phần cuối list nên tớ gán tail lại bởi vì node mới nhất.

Thêm vào sau cùng node bất kỳ

Để thêm 1 node p vào sau cùng node q ngẫu nhiên, thứ nhất tớ cần thiết thám thính tra coi node q sở hữu NULL hay là không, nếu như node q là NULL tức là list trống rỗng, vậy thì tớ tiếp tục thêm vô đầu list. Nếu node q ko NULL, tức là tồn bên trên nhập list, tớ triển khai trỏ p->next = q->next, tiếp sau đó q->next = p. Tiếp theo đuổi tất cả chúng ta đánh giá coi node q trước cơ liệu có phải là node cuối hay là không, nếu như node q là node cuối thì tăng p nhập, p tiếp tục trở nên node cuối nên tớ gán lại tail = p.

void InsertAfterQ(LinkedList& l, Node* p, Node* q)
{
	if (q != NULL)
	{
		p->next = q->next;
		q->next = p;
		if (l.tail == q)
			l.tail = p;
	}
	else
		AddHead(l, p);
}

Danh sách links đơn nhập C++
Thêm thành phần vào sau cùng nút Q nhập danh sách liên kết đơn

Trong hình bên trên, tớ tăng node sở hữu data bởi vì 4 (node p) vào sau cùng node sở hữu data bởi vì 3 (node q). Ta trỏ next của node p nhập next của node q tức là node sở hữu data bởi vì 5, tiếp sau đó trỏ next của node q nhập node p vậy là node p và đã được thêm vô list.

Xóa thành phần ngoài danh sách

Xóa ở đầu

Để xóa thành phần ở đầu list, tớ đánh giá coi list cơ sở hữu trống rỗng hay là không, nếu như trống rỗng, tớ ko cần thiết xóa, trả về thành phẩm là 0. Nếu list ko trống rỗng, tớ triển khai lưu node head lại, tiếp sau đó gán head bởi vì next của node head, tiếp sau đó xóa node head cút. Tiếp theo đuổi tớ cần thiết đánh giá coi list một vừa hai phải bị xóa cút node head sở hữu trống rỗng hay là không, nếu như trống rỗng tớ gán lại tail bởi vì NULL luôn luôn tiếp sau đó trả về thành phẩm 1.

int RemoveHead(LinkedList& l, int& x)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		x = node->data;      // Lưu độ quý hiếm của node head lại
		l.head = node->next;
		delete node;         // Hủy node head đi
		if (l.head == NULL)
			l.tail = NULL;
		return 1;
	}
	return 0;
}

Lưu ý trước lúc xóa node head cút, tớ người sử dụng đổi thay tham ô chiếu x nhằm tàng trữ lại độ quý hiếm của node bị diệt nhằm dùng.

Danh sách links đơn nhập C++
Xóa thành phần đầu danh sách liên kết đơn

Trong hình bên trên, bản thân triển khai xóa node thứ nhất sở hữu data bởi vì 0. Mình trỏ head cho tới next của node 0 (hiện đang được là head), thì head thời điểm hiện tại được xem là node 1, tiếp sau đó bản thân diệt cút node 0 là được.

Xóa ở sau node bất kỳ

Để xóa một node p sau node q ngẫu nhiên, tớ đánh giá coi node q sở hữu NULL hay là không, nếu như node q NULL thì ko tồn bên trên nhập list, vì thế trả về 0, ko xóa. Nếu node q không giống NULL tuy nhiên next của q là NULL, tức là p bởi vì NULL thì ko xóa, trả về 0 (do sau q không tồn tại node nào là cả, q là tail). Nếu node p tồn bên trên, tớ triển khai đánh giá coi node p liệu có phải là tail hay là không, nếu như node p là tail thì gán lại tail là q, tức là node trước cơ nhằm xóa node p cút.

int RemoveAfterQ(LinkedList& l, Node* q, int& x)
{
	if (q != NULL)
	{
		Node* p = q->next;
		if (p != NULL)
		{
			if (l.tail == p)
				l.tail = q;
			q->next = p->next;
			x = p->data;
			delete p;
			return 1;
		}
		return 0;
	}
	return 0;
}

Trong hình bên trên, tớ triển khai xóa node sở hữu data 3 (node p) sau node sở hữu data 2 (node q). Ta trỏ next của node q nhập next của node p tức là node sở hữu data 4, tiếp sau đó xóa node p cút là đoạn.

Duyệt list và in

Sau Khi sở hữu những thao tác tăng, xóa, tất cả chúng ta rất có thể in rời khỏi list nhằm đánh giá coi sở hữu sinh hoạt đích thị hay là không. Để in list, tớ duyệt từ trên đầu cho tới cuối list và in rời khỏi trong khi duyệt. Ta gán một node bởi vì head, tiếp sau đó đánh giá coi node cơ sở hữu NULL hay là không, ko thì in rời khỏi data của node cơ, tiếp sau đó gán tiếp node cơ bởi vì next của nó tức node cơ lúc này là node tiếp theo sau, cứ vì vậy cho tới không còn.

void PrintList(LinkedList l)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		while (node != NULL)
		{
			cout << node->data << ' ';
			node = node->next; // Chuyển sang trọng node tiếp theo
		}
	}
}

Lấy độ quý hiếm node bất kỳ

Để lấy độ quý hiếm thành phần nhập list, tớ triển khai duyệt tương tự động như trong khi in ấn thành phần. Ta sẽ khởi tạo một đổi thay điểm để tìm hiểu địa điểm thời điểm hiện tại, duyệt qua loa những node cho tới Khi node bởi vì NULL hoặc đổi thay điểm bởi vì với địa điểm node cần thiết lấy. Kiểm tra coi nếu như node không giống NULL và đổi thay điểm bởi vì địa điểm cần thiết lấy, tớ tiếp tục trả về vị trí của node cơ, ngược lại trả về NULL (danh sách trống rỗng hoặc là địa điểm cần thiết lấy ở ngoài phạm vi của danh sách).

Node* GetNode(LinkedList& l, int index)
{
	Node* node = l.head;
	int i = 0;
	while (node != NULL && i != index)
	{
		node = node->next;
		i++;
	}
	if (i == index && node != NULL)
		return node;
	return NULL;
}

Tìm thám thính thành phần nhập danh sách

Ý tưởng thám thính tìm kiếm thành phần cũng chính là duyệt list, nếu mà không tìm kiếm thấy thì kế tiếp duyệt. Sau Khi kết giục duyệt, tớ chỉ việc đánh giá coi node duyệt sở hữu bởi vì NULL hay là không, còn nếu như không tức là vẫn nhìn thấy, tớ tiếp tục trả về vị trí của node cơ.

Node* Search(LinkedList l, int x)
{
	Node* node = l.head;
	while (node != NULL && node->data != x)
		node = node->next;
	if (node != NULL)
		return node;
	return NULL;
}

Đếm số thành phần của danh sách

Đếm số thành phần thì cũng tương tự động, tớ vận dụng duyệt từ trên đầu điểm cuối và điểm số node.

int Length(LinkedList l)
{
	int count = 0;
	Node* node = l.head;
	while (node != NULL)
	{
		count++;
		node = node->next;
	}
	return count;
}

Xóa danh sách

Để xóa list, tớ cần thiết diệt toàn bộ những node tức là duyệt và diệt từng node. Tại phía trên bản thân tiếp tục người sử dụng lại hàm RemoveHead. Trước hết, tớ gán một node bởi vì head, đánh giá nếu như node cơ không giống NULL thì gọi RemoveHead và gán lại node bởi vì head tiếp, cứ lặp vì vậy cho tới Khi node cơ NULL thì thôi. Sau Khi xóa không còn toàn bộ thành phần thì gán lại tail bởi vì NULL.

void DestroyList(LinkedList& l)
{
	int x;
	Node* node = l.head;
	while (node != NULL)
	{
		RemoveHead(l, x);
		node = l.head;
	}
	l.tail = NULL;
}

Tổng kết

Vậy là nhập bài xích này, tôi đã reviews với chúng ta về danh sách liên kết đơn và một trong những thao tác cơ bạn dạng bên trên list. Các chúng ta ko nhất thiết cần tuân theo cơ hội của tôi, sở hữu thật nhiều phương pháp để triển khai không giống nhau, chỉ việc chúng ta nắm rõ về con cái trỏ và cấp phép động nhập C++. Nếu thấy hoặc, nhớ rằng share cho tới đồng minh. Cảm ơn chúng ta vẫn theo đuổi dõi bài xích viết!

Xem thêm: cơ quan sinh sản của thực vật có hoa

Source code

LinkedList.hpp

#ifndef LinkedList_hpp
#define LinkedList_hpp

struct Node
{
	int data;
	Node* next;
};

struct LinkedList
{
	Node* head;
	Node* tail;
};

Node* CreateNode(int init_data);
void CreateList(LinkedList& l);
void AddHead(LinkedList& l, Node* node);
void AddTail(LinkedList& l, Node* node);
void InsertAfterQ(LinkedList& l, Node* p, Node* q);
int RemoveHead(LinkedList& l, int& x);
int RemoveTail(LinkedList& l, int& x);
int RemoveAfterQ(LinkedList& l, Node* q, int& x);
Node* GetNode(LinkedList l, int index);
void PrintList(LinkedList l);
Node* Search(LinkedList l, int x);
int Length(LinkedList l);
void DestroyList(LinkedList& l);

#endif

LinkedList.cpp

#include <iostream>
#include "LinkedList.hpp"
using namespace std;

Node* CreateNode(int init_data)
{
	Node* node = new Node;
	node->data = init_data;
	node->next = NULL;
	return node;
}

void CreateList(LinkedList& l)
{
	l.head = NULL;
	l.tail = NULL;
}

void AddHead(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		node->next = l.head;
		l.head = node;
	}
}

void AddTail(LinkedList& l, Node* node)
{
	if (l.head == NULL)
	{
		l.head = node;
		l.tail = node;
	}
	else
	{
		l.tail->next = node;
		l.tail = node;
	}
}

void InsertAfterQ(LinkedList& l, Node* p, Node* q)
{
	if (q != NULL)
	{
		p->next = q->next;
		q->next = p->next;
		if (l.tail == q)
			l.tail = p;
	}
	else
		AddHead(l, p);
}

int RemoveHead(LinkedList& l, int& x)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		x = node->data;
		l.head = node->next;
		delete node;
		if (l.head == NULL)
			l.tail = NULL;
		return 1;
	}
	return 0;
}

int RemoveAfterQ(LinkedList& l, Node* q, int& x)
{
	if (q != NULL)
	{
		Node* p = q->next;
		if (p != NULL)
		{
			if (l.tail == p)
				l.tail = q;
			q->next = p->next;
			x = p->data;
			delete p;
			return 1;
		}
		return 0;
	}
	return 0;
}

Node* GetNode(LinkedList l, int index)
{
	Node* node = l.head;
	int i = 0;
	while (node != NULL && i != index)
	{
		node = node->next;
		i++;
	}
	if (i == index && node != NULL)
		return node;
	return NULL;
}

void PrintList(LinkedList l)
{
	if (l.head != NULL)
	{
		Node* node = l.head;
		while (node != NULL)
		{
			cout << node->data << ' ';
			node = node->next;
		}
	}
}

Node* Search(LinkedList l, int x)
{
	Node* node = l.head;
	while (node != NULL && node->data != x)
		node = node->next;
	if (node != NULL)
		return node;
	return NULL;
}

int Length(LinkedList l)
{
	int count = 0;
	Node* node = l.head;
	while (node != NULL)
	{
		count++;
		node = node->next;
	}
	return count;
}

void DestroyList(LinkedList& l)
{
	int x;
	Node* node = l.head;
	while (node != NULL)
	{
		RemoveHead(l, x);
		node = l.head;
	}
	l.tail = NULL;
}

main.cpp

#include <iostream>
#include "LinkedList.hpp"
using namespace std;

int main()
{
	// Create a linked list
	LinkedList list;
	CreateList(list);

	// Add sample data to tướng list
	Node* node;
	for (auto i = 1; i <= 10; i++)
	{
		// Create new node with init data is i
		node = CreateNode(i);
		
		// Add node to tướng head
		// List that is added node by AddHead will be reversed
		//AddHead(list, node);
		
		// Add node to tướng Tail
		AddTail(list, node);
	}

	// Print list
	PrintList(list);
	cout << endl;

	// Get list's length
	int len = Length(list);
	cout << "Length of list: " << len << endl;

	// Get node at index 7
	Node* nodeAtIdx7 = GetNode(list, 7);
	if (nodeAtIdx7 != NULL)
		cout << "Data at node have idx 7: " << nodeAtIdx7->data << endl;

	// Search for 4 in list
	Node* search4InList = Search(list, 4);
	if (search4InList != NULL)
		cout << "4 was founded" << endl;
	else
		cout << "4 not Found" << endl;

	// Remove node after 4 in list
	int x;
	int res = RemoveAfterQ(list, search4InList, x);
	if (res)
	{
		cout << "Data of node has been removed: " << x << endl;
		cout << "List after removed: ";
		PrintList(list);
		cout << endl;
	}
	else
		cout << "Nothing is removed" << endl;

	// Insert 2409 after node 4
	Node* node2409 = CreateNode(2409);
	InsertAfterQ(list, node2409, search4InList);
	cout << "List after insert 2409 after 4: ";
	PrintList(list);
	cout << endl;
	

	// Remove Head
	res = RemoveHead(list, x);
	if (res)
	{
		cout << "Data of node has been removed: " << x << endl;
		cout << "List after removed head: ";
		PrintList(list);
		cout << endl;
	}
	else
		cout << "Nothing is removed" << endl;

	
	// Destroy all node
	DestroyList(list);
	
	return 0;
}