Linked List Data Structure

A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.

Linked lists can be singly or doubly linked.

Singly linked list

A singly linked list would use a node with data and only one reference (link) to the next node.

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

Full implementation

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

class LinkedList():
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            next_node = self.head
            while next_node.next:
                next_node = next_node.next
            next_node.next = Node(data)

    def push(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
    
    def insert(self, data, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1
                
            new_node = Node(data)
            if prev_node:
                prev_node.next = new_node
                new_node.next = next_node
            else:
                new_node.next = next_node
                self.head = new_node

    def pop(self):
        next_node = self.head
        prev_node = None
        while next_node.next:
            prev_node = next_node
            next_node = next_node.next
        prev_node.next = None
        return next_node.data
    
    def remove(self, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1

            if prev_node:
                prev_node.next = next_node.next
            else:
                self.head = next_node.next

    def reverse(self):
        prev_node = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev_node
            prev_node = current
            current = next_node

        self.head = prev_node
    
    def search(self, data):
        if not self.head:
            return "Not Found"
        else:
            next_node = self.head
            index = 0
            while next_node.data != data:
                next_node = next_node.next
                index += 1
                if not next_node:
                    return "Not Found"
            return index

    def sort(self):
        current_node = self.head
        next_node = None
        if not self.head:
            return
        else:
            while current_node:
                next_node = current_node.next

                while next_node:
                    if current_node.data > next_node.data:
                        current_node.data, next_node.data = next_node.data, current_node.data 
                    next_node = next_node.next
                
                current_node = current_node.next

    def print_list(self):
        next_node = self.head
        while next_node:
            print(next_node.data)
            next_node = next_node.next

import "fmt"

type DataType interface{}

type node struct {
	data DataType
	next *node
}

type LinkedList struct {
	head *node
	length int
}

func (l *LinkedList) IsEmpty() bool {
	return l.length == 0
}

func (l *LinkedList) Size() int {
	return l.length
}

func (l *LinkedList) Add(d DataType) {
	l.length++
	if l.head == nil {
		l.head = &node{d, nil}
	} else {
		temp := l.head
		for temp.next != nil {
			temp = temp.next
		}
		temp.next = &node{d, nil}
	}
}

func (l *LinkedList) Push(d DataType) {
	l.length++
	if l.head == nil {
		l.head = &node{d, nil}
	} else {
		temp := &node{d, nil}
		temp.next = l.head
		l.head = temp
	}
}

func (l *LinkedList) Pop() DataType {
	if l.IsEmpty() {
		return nil
	} else {
		l.length--
		temp := l.head.data
		l.head = l.head.next
		return temp
	}
}

func (l *LinkedList) Reverse() {
	head := l.head.next
	temp := l.head.next
	prev := l.head
	prev.next = nil
	keepGoing := true

	for keepGoing {
		temp = head
		head = head.next
		temp.next = prev
		prev = temp
		if head.next == nil {
			keepGoing = false
		}
	}
	head.next = temp
	l.head = head
}

func (l *LinkedList) PrintList() {
	temp := l.head
	keepGoing := true

	for keepGoing {
		fmt.Println(temp.data)
		if temp.next != nil {
			temp = temp.next
		} else {
			keepGoing = false
		}
	}
}

class Node {
    constructor(data, next=null) {
        this.data = data;
        this.next = next;
    }
}
  
class LinkedList {
    constructor(head=null) {
        this.head = head;
    }
    // add item to end of the list
    append(item) {
        if (this.head === null) {
            this.head = new Node(item);
        } else {
            let next = this.head;
            while (next.next !== null) {
                next = next.next;
            }
            next.next = new Node(item);
        }
    }
    // add item to the front of the list
    push(item) {
        if (this.head === null) {
            this.head = new Node(item);
        } else {
            let temp = new Node(item);
            temp.next = this.head;
            this.head = temp;
        }
    }
    // pop (remove) from end of the list
    pop() {
        let next = this.head;
        let prev = null;
        while (next.next !== null) {
            prev = next;
            next = next.next;
        }
        prev.next = null;
        return next.data;
    }
    // search if node value in list and return bool
    searchNode(item) {
        let next = this.head;
        while (next !== null) {
            if (next.data === item) {
                return true;
            }
            next = next.next;
        }
        return false;
    }
    // traverse list and print each item
    print_list() {
        let next = this.head;
        while (next !== null) {
            print(next.data);
            next = next.next;
        }
    }
    // turn list around
    reverse() {
        let next = this.head;
        let prev = null;
        let curr;
          
        while (next !== null) {
            curr = next;
            next = curr.next;
            curr.next = prev;
            prev = curr;
        }
        this.head = prev;
    }
}

int binarySearch(vector nums, int x) {
	int left = 0;
	int right = nums.size();

	while (left <= right) {
		int mid = left + (right - left) / 2;

		if (nums[mid] == x)
			return mid;
		if (nums[mid] < x)
			left = mid + 1;
		else
			right = mid - 1;
  	}
  	return -1;
}

public class BinarySearch {

    public static int search(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

}

Doubly linked list

A doubly linked list would use a node with data and two references (links) which would point to the next and previous nodes.

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

Full implementation

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

class LinkedList():
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            next_node = self.head
            while next_node.next:
                next_node = next_node.next
            next_node.next = Node(data)

    def push(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
    
    def insert(self, data, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1
                
            new_node = Node(data)
            if prev_node:
                prev_node.next = new_node
                new_node.next = next_node
            else:
                new_node.next = next_node
                self.head = new_node

    def pop(self):
        next_node = self.head
        prev_node = None
        while next_node.next:
            prev_node = next_node
            next_node = next_node.next
        prev_node.next = None
        return next_node.data
    
    def remove(self, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1

            if prev_node:
                prev_node.next = next_node.next
            else:
                self.head = next_node.next

    def reverse(self):
        prev_node = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev_node
            prev_node = current
            current = next_node

        self.head = prev_node
    
    def search(self, data):
        if not self.head:
            return "Not Found"
        else:
            next_node = self.head
            index = 0
            while next_node.data != data:
                next_node = next_node.next
                index += 1
                if not next_node:
                    return "Not Found"
            return index

    def sort(self):
        current_node = self.head
        next_node = None
        if not self.head:
            return
        else:
            while current_node:
                next_node = current_node.next

                while next_node:
                    if current_node.data > next_node.data:
                        current_node.data, next_node.data = next_node.data, current_node.data 
                    next_node = next_node.next
                
                current_node = current_node.next

    def print_list(self):
        next_node = self.head
        while next_node:
            print(next_node.data)
            next_node = next_node.next

Posted on Mar 26, 2019 by bmcculley Posted in:

Data Structures