CODEWITHSUNDEEP
pythonlinked-listcomputer-science
Lexa
Lexa

Reputation: 101

How the linked list works?

I do not have computer science background. I am trying to learn coding by myself, and I'm doing it, partly, by solving the problems on LeetCode.
Anyway, there are the problems that use Linked Lists. And I already found info that linked list have to be simulated in Phython. My problem is that I really cannot get what is behind linked list. For instance, what kind of problems those are suppose to target?
And in general how linked list function. Any link for such info would be really helpfull.
The recent problem I looked at LeetCode asks to swap every two adjacent nodes and return its head. And LeetCode offers following solution, that I cannot actually figure out how it acutaly works. 

# 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

As I said, I do not understand this solution. I tried to use example list 1->2->3->4 that should return list 2->1->4->3 All I managed is to make only one pass through the loop, and then computer should exit the loop, but then what happens? How are the last two numbers switched? How does this code work at all if list has only 2 elements, to me it seems impossible.

If you could just direct me to the online literature that explains something like this, I would be most grateful.

Thanks.

Upvotes: 0

Views: 392

Answers (2)

BretD
BretD

Reputation: 366

Linked lists don't "exist" in Python as the language basically has an iterable builtin list object. Under the hood I'm sure this is implemented as a linked list in C code (most common implementation of Python).

The main feature is that a linked list is easily extendible, wheras an array has to be manually resized if you wish to expand it. Again, in Python these details are all abstracted away. So trying to work an example of linked lists in Python is pointless in my opinion, as you won't learn anything.

You should be doing this in C to get an actual understanding of memory allocation and pointers.

That said, given your example, each ListNode contains a value (like an array), but rather than just that, it has a variable 'next' where you store another ListNode object. This object, just like the first, has a value, and a variable that stores another ListNode object.This can continue for as many objects as desired.

The way the code works is that when we say pre.next, this refers to the ListNode object stored there, and the next object after that is pre.next.next. This works because pre.next is a ListNode object, which has a variable next.

Again, read up on linked lists in C. If you plan to work in higher level languages, I would say you don't really need an understanding of linked lists, as these data structures come "free" with most high level languages.

Upvotes: 2

user3164339
user3164339

Reputation: 166

a linked-list acts almost the same as an array. There are a few main differences though. In a linked-list, the memory used doesn't (and almost never is) contiguous memory. So in an array, if u have 5 items and you look at the memory all 5 items will be right next to each other (for the most part). However each 'item' in a linked list has a pointer that points directly to the next item, removing the need to have contiguous memory. So an array is a 'list' of items that exist contiguously in memory and a linked-list is a 'list' of objects that each hold an item and a pointer to the next item. This is considered a single linked-list as traversal is only possible from one direction. There is also a double linked-list where each node now has a pointer to the next node and another pointer for the previous node allowing traversal from both directions.

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

the link will help you get familiar with visualizing how these linked-lists work. I would probably focus on inserting before and after as these should help you understand what your loop is doing.

Upvotes: 1

Related Questions