Mình đang viết Linked List trong C#. Một trong những yêu cầu là khi xoá một node thì O(1). Gợi ý là dùng địa chỉ. Nếu biết địa chỉ tất nhiên rất dễ xoá. Nhưng khi mình đọc sơ qua thì dùng pointer trong C# là unsafe code. Cho mình hỏi pointer có được dùng thường xuyên trong C# không? Nó unsafe thì có vấn đề với bảo mật. Vậy tại sao lại nên dùng?
C#: Unsafe code
Xóa một node được chỉ định thì nếu là DSLK đơn sẽ vẫn là O(n) vì phải tìm node đằng trước để bứt node bị xóa ra. DSLK đôi mới được, vì kết nối với cả phía trước và phía sau.
Mấy cái này cứ lên MSDN tìm 
https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/unsafe
1 Like
pointer và unsafe ít được dùng trong C# trừ những trường hợp bắt buộc phải dùng mà không có cách nào khác.
Unsafe thì chưa nghe nói liên quan đến bảo mật. Chỉ là cho phép sử dụng những đoạn mã không an toàn-thường có sử dụng pointer.
Và theo MS thì không nên dùng unsafe. Bởi vì đa số các trường hợp sử dụng pointer có thể sử dụng cách khác trong C#.
1 Like
DSLK đơn mà xoá phần tử O(1) thì nó không phải dslk đơn nữa 
1 Like
Xin lỗi mình không nói rõ cái này là DSLK đôi. Nhưng mình không hiểu làm sao viết được hàm xoá để thỏa mãn O(1) trong C#. Các bạn có thể gợi ý cho mình đc ko?
Nếu là C++ thì mình viết hàm có tham số truyền vào là địa chỉ nốt cần xoá, lấy ra nốt phía trước và nốt phía sau của nốt cần xoá rồi chỉnh lại pointer là xong.
Ồ, nếu truyền vào địa chỉ thì C# bạn có thể truyền luôn cả đối tượng vào hàm cơ. Khỏi cần unsafe. Hoặc là bạn viết dưới dạng phương thức, đối tượng tự gọi. Thay vì bạn phải lưu địa chỉ trước, nay bạn phải lưu đối tượng trước 
public class DoubleLinkedList<T>
{
public T value;
public DoubleLinkedList<T> left;
public DoubleLinkedList<T> right;
public DoubleLinkedList(T value)
{
this.value = value;
this.left = null;
this.right = null;
}
public DoubleLinkedList<T> getFirst()
{
var cursor = this;
while (cursor.left != null)
cursor = cursor.left;
return cursor;
}
public DoubleLinkedList<T> getLast()
{
var cursor = this;
while (cursor.right != null)
cursor = cursor.right;
return cursor;
}
public void addToLeft(T value)
{
if (this.left != null)
throw new InvalidOperationException("Node already has left node");
var addedNode = new DoubleLinkedList<T>(value);
this.left = addedNode;
addedNode.right = this;
}
public void addToRight(T value)
{
if (this.right != null)
throw new InvalidOperationException("Node already has right node");
var addedNode = new DoubleLinkedList<T>(value);
this.right = addedNode;
addedNode.left = this;
}
public void addToFirst(T value)
{
var cursor = this.getFirst();
cursor.addToLeft(value);
}
public void addToLast(T value)
{
var cursor = this.getLast();
cursor.addToRight(value);
}
public DoubleLinkedList<T> getNodeAt(int positionFromThis)
{
if (positionFromThis > 0)
{
var cursor = this;
for (var i = 0; i < positionFromThis; i += 1)
{
if (cursor.right == null)
return null;
cursor = cursor.right;
}
return cursor;
}
if (positionFromThis < 0)
{
var cursor = this;
for (var i = 0; i < positionFromThis; i += 1)
{
if (cursor.left == null)
return null;
cursor = cursor.left;
}
return cursor;
}
return this;
}
public void selfRemove()//Cách 1: Dùng method, đối tượng tự lo cho bản thân
{
if (this.left == null)
{
if (this.right == null)
return;
this.right.left = null;
this.right = null;
return;
}
if (this.right == null)
{
this.left.right = null;
this.left = null;
return;
}
this.left.right = this.right;
this.right.left = this.left;
this.left = null;
this.right = null;
}
public override string ToString()
{
var output = new StringBuilder();
var cursor = this.getFirst();
while (cursor.right != null)
{
output.Append(cursor.value + ", ");
cursor = cursor.right;
}
output.Append(cursor.value);
return output.ToString();
}
}
public class Program
{
public static void removeFromList<T>(DoubleLinkedList<T> node)//Cách 2: Dùng static method, truyền đối tượng và tác động vào đối tượng
{
if (node.left == null)
{
if (node.right == null)
return;
node.right.left = null;
node.right = null;
return;
}
if (node.right == null)
{
node.left.right = null;
node.left = null;
return;
}
node.left.right = node.right;
node.right.left = node.left;
node.left = null;
node.right = null;
}
public static void Main(params string[] args)
{
var list = new DoubleLinkedList<int>(5);
list.addToFirst(4);
list.addToFirst(2);
list.addToFirst(3);
list.addToFirst(1);
list.addToLast(7);
list.addToLast(9);
list.addToLast(6);
list.addToLast(8);
Console.WriteLine(list);
var first = list.getFirst();
list.selfRemove();
Console.WriteLine(first);
var next3 = first.getNodeAt(3);
removeFromList(next3);
Console.WriteLine(first);
Console.ReadKey();
}
}
Khi bạn có thể truyền được đối tượng thì bạn có thể sẽ không còn cần phải hiểu “địa chỉ” hay “con trỏ” nữa. Java thậm chí không có con trỏ, C# ban đầu là Java pha C++ nên nó lai tạp thế
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?