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

By Admin 05/06/2024 0

Bài ghi chép được sự được cho phép 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à 1 trong cấu hình tài liệu động, nó là 1 trong list nhưng mà từng thành phần đều links với thành phần trúng sau nó nhập list. Mỗi thành phần (được gọi là 1 trong node hoặc nút) nhập danh sách liên kết đơn là 1 trong cấu hình 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 mật 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 vị NULL.

Tham khảo thêm: việc thực hiện lập trình sẵn c++ lương lậu 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à 1 trong cấu hình tài liệu động, được tạo ra nhờ việc cấp phép động nên nó sở hữu một vài Điểm sáng sau đây:

  • Được cấp phép bộ nhớ lưu trữ Lúc chạy chương trình
  • Có thể thay cho thay đổi độ dài rộng qua quýt việc thêm thắt, xóa phần tử
  • Kích thước tối nhiều tùy theo bộ nhớ 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à vì thế 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 Điểm sáng sau:

  • Chỉ cần thiết bắt được thành phần đầu và cuối là hoàn toàn có thể vận hành được danh sách
  • Truy cập cho tới thành phần tình cờ nên duyệt từ trên đầu cho tới địa điểm đó
  • Chỉ hoàn toàn có thể thăm dò tìm tòi tuyến tính một trong những phần tử

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

Trước Lúc lên đường nhập thiết lập danh sách liên kết đơn, hãy chắc chắn rằng rằng các bạn 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à 1 trong cấu hình 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 các bạn nắm được nội dung bài viết này. Nếu các bạn cảm nhận thấy ko thoải mái 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 giờ đây thì chính thức thôi!

Tạo node

Danh sách links đơn được tạo ra trở nên từ khá nhiều node, vì thế, tất cả chúng ta tiếp tục nằm trong lên đường 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 hoàn toàn có thể là loại tài liệu đã có sẵn hoặc các bạn tự động khái niệm (struct hoặc class…), nhập nội dung bài viết này nhằm đơn giản và giản dị bản thân tiếp tục dùng loại int mang lạ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 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 ra một node mới nhất, tớ tiến hành cấp phép động mang lại node mới nhất, khởi tạo ra độ quý hiếm ban sơ 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 ra ko thêm nữa list nên ko links với thành phần này cả nên phần links gán vị NULL
	return node;
}

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

Ta vẫn đã có được bộ phận tạo ra danh sách liên kết đơn là node, tiếp 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 kế tiếp vậy nên mô tả chỉ nên biết thành phần đầu và cuối là hoàn toàn có thể vận hành được list này. Vậy đơn giản và giản dị tớ cần thiết tạo ra một cấu hình 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 ra list, list tiếp tục không tồn tại thành phần này, vì thế head và tail ko trỏ nhập đâu cả, tớ tiếp tục gán bọn chúng vị NULL. Ta thiết kế hàm tạo ra 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 vị NULL

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

Thêm nhập đầu

Để thêm thắt node nhập đầu list, thứ nhất tớ cần thiết thăm dò 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 vị node cơ. trái lại nếu như list ko trống rỗng, tớ tiến hành trỏ bộ phận links nhập head, tiếp sau đó gán lại head 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 thêm thắt node sở hữu data vị 0 nhập list. Ta tiến hành 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 vị 1), tiếp sau đó tớ trỏ head nhập node sở hữu data 0 vừa mới được thêm thắt. Vậy là thành phần này đã nằm ở vị trí đầu list rồi.

Thêm nhập cuối

Tương tự động, nhằm thêm thắt node vào thời điểm 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 vị node mới nhất. Nếu ko trống rỗng, tớ tiến hành trỏ tail->next nhập node mới nhất, tiếp sau đó gán lại tail vị node mới nhất (vì giờ đây node mới nhất thêm thắt đó 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 điểm cuối danh sách liên kết đơn

Xem thêm: trường đại học lao đông xã hội

Trong hình bên trên, tất cả chúng ta tiến hành thêm thắt node sở hữu data vị 6 nhập list. Tail lúc này là node sở hữu data 5, tiến hành gán tail->next vị node mới nhất nhằm nối thêm thắt nó nhập đuôi list, thời điểm hiện nay node mới nhất trở nên thành phần cuối list nên tớ gán tail lạ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 dò 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 nữa đầu list. Nếu node q ko NULL, tức là tồn bên trên nhập list, tớ tiến hành trỏ p->next = q->next, tiếp sau đó q->next = p. Tiếp bám theo 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ì thêm thắt 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ớ thêm thắt node sở hữu data vị 4 (node p) vào sau cùng node sở hữu data 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 vị 5, tiếp sau đó trỏ next của node q nhập node p vậy là node p và được thêm nữa 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ớ tiến hành lưu node head lại, tiếp sau đó gán head vị next của node head, tiếp sau đó xóa node head lên đường. Tiếp bám theo tớ cần thiết đánh giá coi list một vừa hai phải bị xóa lên đường 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 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 lên đường, tớ người sử dụng biến đổi tham ô chiếu x nhằm tàng trữ lại độ quý hiếm của node bị bỏ 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 tiến hành xóa node thứ nhất sở hữu data 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 nay được xem là node 1, tiếp sau đó bản thân bỏ lên đường 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 vị NULL thì ko xóa, trả về 0 (do sau q không tồn tại node này cả, q là tail). Nếu node p tồn bên trên, tớ tiến hành đá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 lên đường.

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ớ tiến hành 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 lên đường là đoạn.

Duyệt list và in

Sau Lúc sở hữu những thao tác thêm thắt, xóa, tất cả chúng ta hoàn toàn có thể in đi ra list nhằm đánh giá coi sở hữu hoạt động và sinh hoạt trúng hay là không. Để in list, tớ duyệt từ trên đầu cho tới cuối list và in đi ra trong những khi duyệt. Ta gán một node vị head, tiếp sau đó đánh giá coi node cơ sở hữu NULL hay là không, ko thì in đi ra data của node cơ, tiếp sau đó gán tiếp node cơ vị next của nó tức node cơ giờ đây là node tiếp sau, cứ như thế 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ớ tiến hành duyệt tương tự động như khi in ấn thành phần. Ta sẽ khởi tạo một biến đổi điểm để hiểu địa điểm lúc này, duyệt qua quýt những node cho tới Lúc node vị NULL hoặc biến đổi điểm 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à biến đổi điểm 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 dò thành phần nhập danh sách

Ý tưởng thăm dò tìm tòi 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 Lúc kết thúc giục duyệt, tớ chỉ việc đánh giá coi node duyệt sở hữu vị NULL hay là không, 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 bỏ toàn bộ những node tức là duyệt và bỏ 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 vị head, đánh giá nếu như node cơ không giống NULL thì gọi RemoveHead và gán lại node vị head tiếp, cứ lặp như thế cho tới Lúc node cơ NULL thì thôi. Sau Lúc xóa không còn toàn bộ thành phần thì gán lại tail 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 bác này, tôi đã reviews với chúng ta về danh sách liên kết đơn và một vài thao tác cơ bạn dạng bên trên list. Các các bạn ko nhất thiết nên tuân theo cơ hội của tớ, sở hữu thật nhiều phương pháp để tiến hành không giống nhau, chỉ việc các bạn 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 mang lại bằng hữu. Cảm ơn chúng ta vẫn bám theo dõi bài bác viết!

Xem thêm: từ đồng nghĩa với từ

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 lớn list
	Node* node;
	for (auto i = 1; i <= 10; i++)
	{
		// Create new node with init data is i
		node = CreateNode(i);
		
		// Add node lớn head
		// List that is added node by AddHead will be reversed
		//AddHead(list, node);
		
		// Add node lớn 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;
}