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

By Admin 07/04/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 cấu tạo tài liệu động, nó là 1 list tuy nhiên 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à 1 node hoặc nút) nhập danh sách liên kết đơn là 1 cấu tạo sở hữu nhì trở thành phần:

  • Thành phần dữ liệu: lưu vấn đề về phiên bản thân thuộc thành phần bại liệt.
  • 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 sau cuối thì bộ phận này tự NULL.

Tham khảo thêm: việc thực hiện thiết kế c++ 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à 1 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 số trong những điểm sáng sau đây:

  • Được cấp phép bộ lưu trữ Khi chạy chương trình
  • Có thể thay cho thay đổi độ dài rộng qua loa việc thêm thắt, 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à tự 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ể quản lý và 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ể lần kiếm tuyến tính một trong những phần tử

Cài bịa đặt danh sách liên kết đơn

Trước Khi lên đường nhập thiết lập danh sách liên kết đơn, hãy chắc hẳ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à 1 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 rất rất khó khăn nhằm chúng ta hiểu rõ 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 giờ đây thì chính thức thôi!

Tạo node

Danh sách links đơn được tạo nên trở thành 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 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 đơ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 nên một node mới mẻ, tao tiến hành cấp phép động mang lại node mới mẻ, khởi tạo nên độ 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 vừa vặn tạo nên 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 tự NULL
	return node;
}

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

Ta vẫn đạt được bộ phận tạo thành danh sách liên kết đơn là node, tiếp sau tất cả chúng ta cần thiết quản lý và 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 miêu tả chỉ cần phải biết thành phần đầu và cuối là hoàn toàn có thể quản lý và vận hành được list này. Vậy đơn giản và giản dị tao 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 mẻ tạo nên 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ả, tao tiếp tục gán bọn chúng tự 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ờ muốn tạo một list, tao thực hiện như sau:

LinkedList list;
CreateList(list); // Gán head và tail tự 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 tao cần thiết lần tra coi list bại liệt sở hữu trống rỗng hay là không, nếu như list trống rỗng, tao chỉ việc gán head và tail của list tự node bại liệt. trái lại nếu như list ko trống rỗng, tao tiến hành trỏ bộ phận links nhập head, tiếp sau đó gán lại head tự node mới mẻ.

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 tự 0 nhập list. Ta tiến hành trỏ next của node bại liệt nhập head của list (chính là node thứ nhất của list sở hữu data tự 1), tiếp sau đó tao 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 tại 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 gian cuối list, thứ nhất tao đánh giá coi list trống rỗng hay là không, trống rỗng thì gán head và tail đều tự node mới mẻ. Nếu ko trống rỗng, tao tiến hành trỏ tail->next nhập node mới mẻ, tiếp sau đó gán lại tail tự node mới mẻ (vì giờ đây node mới mẻ 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 gian cuối danh sách liên kết đơn

Xem thêm: trong phong trào dân chủ 1936 đến 1939 nhân dân việt nam đã

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 tự 6 nhập list. Tail lúc này là node sở hữu data 5, tiến hành gán tail->next tự node mới mẻ nhằm nối thêm thắt nó nhập đuôi list, thời điểm hiện nay node mới mẻ phát triển thành thành phần cuối list nên tao gán tail lại tự node mới mẻ.

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 tao cần thiết lần 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ì tao 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, tao tiến hành trỏ p->next = q->next, tiếp sau đó q->next = p. Tiếp theo dõi tất cả chúng ta đánh giá coi node q trước bại liệt 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ở thành node cuối nên tao 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, tao thêm thắt node sở hữu data tự 4 (node p) vào sau cùng node sở hữu data tự 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 tự 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, tao đánh giá coi list bại liệt sở hữu trống rỗng hay là không, nếu như trống rỗng, tao ko cần thiết xóa, trả về sản phẩm là 0. Nếu list ko trống rỗng, tao tiến hành lưu node head lại, tiếp sau đó gán head tự next của node head, tiếp sau đó xóa node head lên đường. Tiếp theo dõi tao cần thiết đánh giá coi list vừa vặn 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 tao gán lại tail tự NULL luôn luôn tiếp sau đó trả về sản 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, tao người sử dụng trở nên tham lam 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 tự 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, tao đá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 tự 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, tao 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 bại liệt 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, tao 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 Khi 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 sinh hoạt đích thị hay là không. Để in list, tao duyệt từ trên đầu cho tới cuối list và in đi ra trong khi duyệt. Ta gán một node tự head, tiếp sau đó đánh giá coi node bại liệt sở hữu NULL hay là không, ko thì in đi ra data của node bại liệt, tiếp sau đó gán tiếp node bại liệt tự next của nó tức node bại liệt giờ đây là node tiếp 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 lịch sự 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, tao 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 trở nên điểm để tìm hiểu địa điểm lúc này, duyệt qua loa những node cho tới Khi node tự NULL hoặc trở nên điểm tự 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à trở nên điểm tự địa điểm cần thiết lấy, tao tiếp tục trả về vị trí của node bại liệt, 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 lần thành phần nhập danh sách

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

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, tao 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, tao cần thiết bỏ toàn bộ những node tức là duyệt và bỏ từng node. Tại trên đây bản thân tiếp tục người sử dụng lại hàm RemoveHead. Trước hết, tao gán một node tự head, đánh giá nếu như node bại liệt không giống NULL thì gọi RemoveHead và gán lại node tự head tiếp, cứ lặp vì vậy cho tới Khi node bại liệt 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 tự 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 đã trình làng với chúng ta về danh sách liên kết đơn và một số trong những thao tác cơ phiên bản bên trên list. Các chúng ta 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 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, hãy nhờ rằng share mang lại đồng chí. Cảm ơn chúng ta vẫn theo dõi dõi bài xích viết!

Xem thêm: km, m, dm, cm, mm

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 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 to lớn head
		// List that is added node by AddHead will be reversed
		//AddHead(list, node);
		
		// Add node to 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;
}