链表与阵列-IGI

时间：2020-02-23 14:41:33 　来源:igfitidea点击:

链表和数组可能是最基本的数据结构，但是它们的使用通常会造成混乱。
使用适当的数据结构通常可以使代码更简单，更有效。
在数据结构中，链表与数组也是一个流行的访谈问题。

链表与阵列

本文将提供这两种数据结构的深入比较。

我们将基于以下属性对其进行比较：

定义和结构
操作和时间复杂度分析
内存分析
代码(C和Python)

1.定义和结构

链表是一种通过引用存储线性连接的非连续数据的数据结构。
这意味着链接列表的每个节点都将包含对其下一个和/或者上一个节点的引用。
这有助于形成线性连接的节点链，但是在内存中，它们可能不在连续的段中。

数组是一种具有固定大小的数据结构，包含可通过索引引用的相似类型的数据的集合。
这意味着在使用数组之前，我们必须定义其大小和类型，在存储数据之后，我们可以使用索引来引用它。

在内存中，数组也存在于连续的数据块中.2D数组

2.运营和时间复杂度分析

我们将根据以下操作比较数据结构：

插入和删除
访问元素

插入和删除

可以在开头，中间或者结尾处完成"链接列表"中的插入和删除操作。

如果插入或者删除是在开始时完成的，那么我们只需要在开头重新分配引用，这就是O(1)操作。
如果插入或者删除是在中间或者结尾完成的，那么我们首先需要在O(N)时间到达所需位置，然后在O(1)时间重新分配引用。
这需要O(N +1)= O(N)时间。

链表插入

对于一个数组，无论插入或者删除完成什么地方，我们总是需要移动数组的其余部分来平衡索引，因此这些操作花费O(1)时间进行操作，花费O(N)时间平衡索引。
因此，总是需要O(N + 1)= O(N)时间。

访问元素

在链接列表中，要访问元素，我们必须从开始经过O(N)时间的遍历来达到其位置。

在数组中，我们有可以直接引用的索引。
这很有用，因为现在我们不必进行遍历，因此访问需要O(1)时间。

3.记忆分析

链表几乎总是一种更节省内存的方式来存储数据。
这是因为我们动态分配了链表中的数据，并且可以根据用途缩小和扩展其大小。

另一方面，数组始终具有固定大小。
如果未为元素分配任何值，则它仍将保留为数组的一部分，并且仍将消耗内存。

但这并不意味着数组总是效率较低。
数组仅占用分配给它们的内存，而"链接列表"将占用用于存储数据以及存储引用的内存。
另外，对于某些操作(如排序)，我们需要另外的空间来存储和移动元素，这在数组中很有效。

链表实现

1. Python

class Node:

  def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList:
  """
  Initialize the list by assigning
  head = NULL.
  """

  def __init__(self):
      self.head = None

  '''
  Returns the linear traversal of the
  Linked List in the form of a list.

  Initially, we can define a node that 
  points to the head of the linked list
  and then we can keep sending it forward 
  in the Linked List till we don't hit an end.
  '''

  def traverse_list(self):

      # Node that points to the head, initially.
      cur = self.head
      ret = []

      # Loop to send the cur node to the end.
      while cur:
          ret.append(cur.data)
          cur = cur.next

      # Returns the Linear Traversal in a list.
      return ret

  '''
  To insert a node, we have 3 cases:
  1) Empty List
  2) Insertion at the beginning
  3) Insertion in the middle/at the end

  For insertion at the end, we can loop till
  one element before the required position 
  and then do the relinking of references.
  '''

  def insert_node(self, pos, data):

      new_node = Node(data)
      cur_node = self.head

      # Case 1 : Empty List
      if cur_node is None:
          self.head = new_node

      # Case 2: Insertion at the beginning
      elif pos == 0:
          new_node.next = self.head
          self.head = new_node

      # Case 3: Insertion in the middle/at the end
      else:
          while pos - 1 > 0 and cur_node.next is not None:
              cur_node = cur_node.next
              pos -= 1

          next_node = cur_node.next
          new_node.next = next_node
          cur_node.next = new_node

      return True

  '''
  To delete a node, we have 5 cases:
  1) Deletion from Empty List
  2) Deletion at the beginning
  5) Delete a node that does not exist
  3) Deletion at the end
  4) Deletion in the middle

  For deletion of a node, we first reach
  one node before the required position
  through a linear traversal and then relink
  the references accordingly.
  '''

  def remove_node(self, pos):

      # Case 1 : Empty List
      if self.head is None:
          return False

      # Case 2 : Deletion at beginning
      elif pos == 0:
          self.head = self.head.next
          return True

      else:
          cur = self.head
          while pos - 1 > 0 and cur is not None:
              cur = cur.next
              pos -= 1

          # Case 3 : Delete a node that does not exist
          if cur is None:
              return False

          # Case 4: Deletion at the end
          elif cur.next is None:
              cur = self.head
              while cur.next.next is not None:
                  cur = cur.next
              cur.next = None
              return True

          # Case 5 : Deletion in the middle
          cur.next = cur.next.next
          return True

a = LinkedList()
a.insert_node(0, 3)
a.insert_node(0, 2)
a.insert_node(0, 1)
print("Linked List :", a.traverse_list())
a.remove_node(2)
print("Linked list :", a.traverse_list())

输出

2. C

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct node{
  int data;
  struct node *next;
} *head = NULL;

struct node *make_node(int data){
  struct node *new = (struct node *)malloc(sizeof(struct node));
  new->next = NULL; 
  new->data = data;
  return new;
}

/*
To insert a node, we have 3 cases:
1) Empty List
2) Insertion at the beginning
3) Insertion in the middle/at the end

For insertion at the end, we can loop till
one element before the required position 
and then do the relinking of references.
*/

bool insertNode(int pos, int data){
  struct node *newNode = make_node(data), *curNode = head;

  //Case 1 : Empty List
  if(curNode == NULL){
      head = newNode;
  }

  //Case 2: Insertion at the beginning
  else if(pos == 0){
      newNode->next = head;
      head = newNode;
  }

  //Case 3: Insertion in the middle/at the end
  else{
      while(pos - 1 > 0 && curNode->next != NULL){
          curNode = curNode->next;
          pos--;
      }
      newNode->next = curNode->next;
      curNode->next = newNode;
  }

  return true;
}

/*
Initially we can define a node that 
points to the head of the linked list
and then we can keep sending it forward 
in the Linked List till we don't hit an end.
*/
void traverseList(){
  struct node *cur = head;
  while(cur){
      printf("%d ", cur->data);
      cur = cur->next;
  }
  printf("\n");
}

/*
To delete a node, we have 5 cases:
1) Deletion from Empty List
2) Deletion at the beginning
5) Delete a node that does not exist
3) Deletion at the end
4) Deletion in the middle

For deletion of a node, we first reach
one node before the required position
through a linear traversal and then relink
the references accordingly.
*/

bool removeNode(int pos){

  struct node *cur;

  //Case 1 : Empty List
  if(head == NULL)
      return false;

  //Case 2 : Deletion at beginning
  else if (pos == 0){
      head = head->next;
      return true;
  }

  else{

      cur = head;
      while (pos - 1 > 0 && cur != NULL){
          cur = cur->next;
          pos--;
      }

      //Case 3 : Delete a node that does not exist
      if(cur == NULL)
          return false;

      //Case 4: Deletion at the end
      else if(cur->next == NULL){
          cur = head;
          while(cur->next->next != NULL){
              cur = cur->next;
          }
          cur->next = NULL;
          return true;
      }

      //Case 5 : Deletion in the middle
      cur->next = cur->next->next;
      return true;
  }
}

int main(){

  insertNode(0, 3);
  insertNode(0, 2);
  insertNode(0, 1);

  traverseList();
  removeNode(3);
  traverseList();

  return 0;
}

数组实现

1. Python

N = 10
singleDimensionalArray = [0 for i in range(N)]
multiDimensionalArray = [[0 for x in range(N)] for y in range(N)]

A = 4
pos = 5
singleDimensionalArray[pos] = A

X, Y = 2, 3
multiDimensionalArray[X][Y] = A

print(singleDimensionalArray)

for i in multiDimensionalArray:
  print(i)

2. C

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define N 5

int main(){

  int singleDimensionalArray[N] = {0};
  int multiDimensionalArray[N][N] = {0};

  int A = 4;
  int pos = 3, X = 2, Y = 3;

  singleDimensionalArray[pos] = A;
  multiDimensionalArray[X][Y] = A;

  int i, j;
  for(i = 0; i < N; i++){
      printf("%d ", singleDimensionalArray[i]);
  }
  printf("\n\n");

  for(i = 0; i < N; i++){
      for(j = 0; j < N; j++){
          printf("%d ", multiDimensionalArray[i][j]);
      }
      printf("\n");
  }

  return 0;
}

链表与阵列