Khi được sử dụng với vai trò cấu trúc dữ liệu, đối thủ chính của ma trận kề là danh sách kề. Do mỗi ô trong ma trận kề chỉ đòi hỏi một bit, nên chúng có thể được biểu diễn bằng một cách rất gọn, chỉ chiếm n2/8 byte bộ nhớ liên tục, trong đó n là số đỉnh. Ngoài việc tiết kiệm bộ nhớ, lưu trữ gọn gàng này còn khuyến khích locality of reference (tính địa phương của các truy nhập đến bộ nhớ).