リンクされたリストの仕組みは？

Question

私はコンピュータ科学のバックグラウンドを持っていません。私は自分でコーディングを学ぼうとしていますが、私はLeetCodeの問題を解決することによってそれをやっています。
とにかく、リンクされたリストを使用する際に問題があります。そして、私は既にPhythonでリンクリストをシミュレートしなければならないという情報を発見しました。私の問題は、本当にリンクされたリストの後ろにあるものを得ることができないということです。例えば、それらが対象としている問題の種類は？
一般的にどのようにリンクされたリスト機能。そのような情報のリンクは本当に役に立つでしょう。
私がLeetCodeを見ている最近の問題は、2つの隣接ノードを交換してその頭を返すように求めています。 LeetCodeは次のようなソリューションを提供しています。

# Definition for singly-linked list. 
# class ListNode(object): 
#  def __init__(self, x): 
#   self.val = x 
#   self.next = None 

class Solution(object): 
    def swapPairs(self, head): 
     """ 
     :type head: ListNode 
     :rtype: ListNode 
     """ 
     pre = self 
     pre.next = head 
     while pre.next and pre.next.next: 
      a = pre.next 
      b = a.next 
      pre.next =b 
      b.next =a 
      a.next =b.next 
      pre = a 
     return self.next 

私が言ったように、私はこの解決策を理解していません。私は、リスト2-> 1-> 4-> 3を返すべきリストリスト1-> 2-> 3-> 4を使用しようとしました。 私が管理したのは、ループを1回だけ通過させ、ループですが、どうなりますか？最後の2つの番号はどのように切り替わりますか？リストに2つの要素しかない場合、このコードはどのように動作しますか？私には不可能です。

このようなことを説明するオンライン資料に私を誘導することができれば、私は最も感謝しています。

ありがとうございました。

Answer 1

linked-listは配列とほぼ同じように動作します。しかし、いくつかの主な違いがあります。リンクされたリストでは、使用されるメモリは連続しないメモリではありません。だから配列では、あなたは5つのアイテムを持っているとあなたは5つのアイテムのすべてのお互いの隣に（ほとんどの場合）になりますメモリを見てください。しかし、リンクされたリストの各「項目」には、次の項目を直接指すポインタがあり、連続したメモリを持つ必要はありません。したがって、配列はメモリ内に連続して存在するアイテムの 'リスト'であり、リンクされたリストはそれぞれアイテムを保持するオブジェクトのリストと次のアイテムへのポインタです。トラバーサルは1つの方向からのみ可能であるため、これは単一のリンクリストと見なされます。また、各ノードが今度は次のノードへのポインタと前のノードに対する別のポインタを持ち、双方向からのトラバーサルを可能にするダブルリンクリストがあります。

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

リンクはあなたがこれらのリンクされたリストがどのように機能するかを視覚化するに慣れるのに役立ちます。私はおそらく前後に挿入することに焦点を合わせます。これはループが何をしているのか理解するのに役立つはずです。

Answer 2

リンクリストは基本的に反復可能な組み込みリストオブジェクトを持つため、Pythonでは「存在しません」。フードの下では、これはCコードのリンクリスト（Pythonの最も一般的な実装）として実装されていると確信しています。

主な特徴は、リンクされたリストを簡単に拡張できることです。拡張する場合は、配列のサイズを手動で変更する必要があります。 Pythonでは、これらの詳細はすべて抽象化されています。だから、あなたが何も学んでいないので、Pythonでリンクリストの例を試してみることは、私の意見では無意味です。

メモリ割り当てとポインタの実際の理解を得るには、Cでこれを行う必要があります。それぞれのListNodeには値（配列など）が含まれていますが、それだけではなく、別のListNodeオブジェクトを格納する変数 'next'があります。このオブジェクトは、最初のものと同じように、値を持ち、別のListNodeオブジェクトを格納する変数です。これは、必要な数のオブジェクトに対して続けることができます。

コードの仕組みは、私たちがpreと言うときです。次に、そこに格納されているListNodeオブジェクトを参照し、そのあとの次のオブジェクトはpre.next.nextです。これは、pre.nextが次の変数を持つListNodeオブジェクトであるために機能します。

また、C言語のリンクリストを読んでください。より高いレベルの言語で作業する予定がある場合は、リンクリストを理解する必要はありません。これらのデータ構造は、レベルの言語。